How can I spend less memory on this graph problem?

Question

How can I spend less memory on this graph problem?

Navigation

#1 by (0 votes)

0

#include<iostream>
#include<vector>
#include<cstring>

#define TAM 1000000

using namespace std;

void dfs( int,bool[] );

vector<int> adj[TAM];

int cont, N;

int main( ) {
  int I,i,a,b,p;
  char oso;

  cin >> N >> I;

  bool visit[N] = { false };

  while( I-- ) {
    cin >> oso;

    switch( oso ) {
    case 'A':
      cin >> a >> b;
      adj[a].push_back( b );
      adj[b].push_back( a );
      break;

    case 'E':
      cin >> p;
      cont = 1;
      dfs( p, visit );
      memset( visit, 0, N * I );
      cout << cont << endl;
      break;      
    }     
  }
}

void dfs( int nodo,bool visit[] ) {
  visit[nodo] = true;

  for( auto &k:adj[nodo] ) {
    if( visit[k] == false ) {
      dfs(k,visit);
      ++cont;
    }
  }
}

c++ array

asked by Osvaldo Santos 12.10.2018 в 09:27

source

1 answer

DireBaseDataBase in a Fragment I was not activated timepicker (materialize)

score 0 · Answer 1

You do not give too much context about the problem you're working on, but by looking at the code, the adjacent matrix could be much smaller: if "a" is adjacent to "b", then "b" is adjacent to "a", as you can see in these two lines of code:

  adj[a].push_back( b );
  adj[b].push_back( a );

This means that you could save only if "a" is adjacent to "b", because if this is the case, "b" is adjacent to "a":

adj[a].push_back( b );

Thus the size of the adj would be much smaller (instead of being an MxM matrix, it could only be a vector of size M)