Cod sursa(job #660086)

Utilizator suzanicaSuzanica Mihu suzanica Data 11 ianuarie 2012 18:34:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <vector>

using namespace std;

const int MAX_N = 100002;
const char infile[] = "dfs.in";
const char outfile[] = "dfs.out";

vector < int > G[ MAX_N ];
int use[ MAX_N ];
int N, M, nr_comp;

void read(){
	FILE *f;
	int x, y;
	f = fopen( infile, "rt" );
	fscanf( f, "%d %d", &N, &M );
	for( ; M; M-- ){
		fscanf( f, "%d %d", &x, &y );
		G[ x ].push_back(y);
		G[ y ].push_back( x );
	}
}

void dfs( int node ){
	vector < int > :: iterator it;
	use[ node ] = 1;
	for( it = G[ node ].begin(); it != G[ node ].end(); ++it )
		if( !use[ *it ] )
			dfs( *it );
}

void write(){
	FILE *g;
	g = fopen( outfile, "wt" );
	fprintf( g, "%d\n", nr_comp );
}

int main(){
	read();
	for( int i = 1; i <= N; ++i )
		if( !use[ i ] )
			dfs( i ), nr_comp++;
	write();
	return 0;
}