Cod sursa(job #2506587)

Utilizator euyoTukanul euyo Data 8 decembrie 2019 14:28:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <vector>
#define MAXN 100111
 
using namespace std;
 
vector<int> adjl[MAXN];
 
char viz[MAXN];
 
void DFS( int node ) {
  int i;
	viz[node]=1;
 
  for ( i = 0; i < adjl[node].size(); ++i ) {
    if ( viz[adjl[node][i]] != 1 ) {
      DFS( adjl[node][i] );
    }
  }
}
 
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 = 1; i <= n; ++i ) {
    if ( viz[i] != 1 ) {
      DFS( i );
      ++comp;
    }
  }
  fprintf( fout, "%d", comp );
  fclose( fin );
  fclose( fout );
  return 0;
}