Cod sursa(job #2029042)

Utilizator ReksioCroftOctavian Florin Staicu ReksioCroft Data 29 septembrie 2017 08:44:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <vector>
#include <bitset>
#define nmax 100000
using namespace std;
vector <int> v[nmax];
bitset <nmax> verif;
int co;

void dfs( int nod ) {
  verif[nod] = 1;
  for ( int i = 0; i < v[nod].size(); i++ ) {
    if( verif[v[nod][i]] == 0 ) {
      verif[v[nod][i]] = 1;
      dfs( v[nod][i] );
    }
  }
}

int main() {
  int n, m, i, x, y;
  FILE *fin, *fout;
  fin = fopen( "dfs.in", "r" );
  fscanf( fin, "%d%d", &n, &m );
  for ( i = 0; i < m; i++ ) {
    fscanf( fin, "%d%d", &x, &y );
    x--;y--;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  fclose( fin );
  for ( i = 0; i < n; i++ ) {
    if ( verif[i] == 0 ) {
      co++;
      dfs( i );
    }
  }
  fout = fopen( "dfs.out", "w" );
  fprintf( fout, "%d\n", co );
  fclose( fout );
  return 0;
}