Cod sursa(job #164208)

Utilizator tvladTataranu Vlad tvlad Data 23 martie 2008 17:49:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <cstdio>
#include <vector>
using namespace std;

const int N = 100000;

int n,m, nc;
vector<int> g[N];
vector<bool> used;

void df ( int x ) {
	used[x] = true;
	for (int i = 0; i < g[x].size(); ++i)
		if (!used[g[x][i]])
			df(g[x][i]);
}

int main() {
	freopen("dfs.in","rt",stdin);
	freopen("dfs.out","wt",stdout);
	scanf("%d %d",&n,&m);
	for (int i = 0; i < m; ++i) {
		int f,t;
		scanf("%d %d",&f,&t);
		--f; --t;
		g[f].push_back(t);
		g[t].push_back(f);
	}
	nc = 0;
	used.resize(n,false);
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			++nc;
			df(i);
		}
	}
	printf("%d\n",nc);
	return 0;
}