Cod sursa(job #151980)

Utilizator amadaeusLucian Boca amadaeus Data 8 martie 2008 20:56:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#include <vector>

using namespace std;

#define NX 100010
#define pb push_back
#define tr(X,i) \
	for( vi::iterator i = X.begin(); i != X.end(); i++ )

typedef vector< int > vi;

vi G[ NX ];
int V, E, col[ NX ], k;

void cit() {
	int u, v;
	
	scanf( "%d%d", &V, &E );
	for( ; E; E-- ) {
		scanf( "%d%d", &u, &v );
		G[ u ].pb( v );
		G[ v ].pb( u );
	}
}

void DFS( int u ) {
	col[ u ] = 1;
	tr( G[u], v )
		if( col[ *v ] == 0 )
			DFS( *v );
}

void rez() {
	int i;
	for( i = 1, k = 0; i <= V; i++ )
		if( col[ i ] == 0 )
			k++, DFS( i );
}

void scr() {
	printf( "%d\n", k );
}

int main() {
	freopen( "dfs.in", "r", stdin );
	freopen( "dfs.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}