Cod sursa(job #2505960)

Utilizator euyoTukanul euyo Data 7 decembrie 2019 12:19:24
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <vector>
#define MAXN 100000

using namespace std;

vector<int> adjl[MAXN];

int st[MAXN];
char viz[MAXN];
int sp;

void DFS( int node ) {
  int i;

  for ( i = 0; i < adjl[node].size(); ++i ) {
    if ( viz[adjl[node][i]] != 1 ) {
      st[sp] = adjl[node][i];
      ++sp;
      viz[adjl[node][i]] = 1;
      DFS( adjl[node][i] );
      --sp;
    }
  }
}

int main() {
  FILE *fin = fopen( "dfs.in", "r" );
  FILE *fout = fopen( "dfs.out", "w" );
  int n, m, x, y, i, j, comp;

  fscanf( fin, "%d%d", &n, &m );
  for ( i = 0; i < m; ++i ) {
    fscanf( fin, "%d%d", &x, &y );
    adjl[x].push_back( y );
    adjl[y].push_back( x );
  }
  comp = 0;
  for ( i = 0; i < n; ++i ) {
    st[sp] = i;
    ++sp;
    if ( viz[i] != 1 ) {
      DFS( i );
      ++comp;
    }
    --sp;
  }
  fprintf( fout, "%d", comp );
  fclose( fin );
  fclose( fout );
  return 0;
}