Cod sursa(job #146451)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 1 martie 2008 18:47:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const long MAX = 100010;
long U[MAX];
vector<long> G[MAX];
long n,m,nr;

void dfs(long x) {
	if ( U[x] ) return;
	U[x] = true;
	for_each(G[x].begin(), G[x].end(), dfs);
}

int main() {
	freopen("dfs.in", "r", stdin);
	scanf("%ld %ld", &n, &m);
	while ( m-- ) {
		long x,y;
		scanf("%ld %ld", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	fclose(stdin);

	for (long i=1; i<=n; ++i)
		if ( !U[i] ) 
			nr++, dfs(i);

	fprintf(fopen("dfs.out","w"), "%ld\n", nr);
	return 0;
}