Cod sursa(job #211461)

Utilizator vlad_popaVlad Popa vlad_popa Data 2 octombrie 2008 13:01:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 100005
#define pb push_back

int N, M;
int viz[MAXN];
int cnt;
vector<int> G[MAXN];

void dfs (int nod){
	for (vector<int> :: iterator it = G[nod].begin(); it != G[nod].end(); ++ it)
		if (!viz[*it]) viz[*it] = cnt, dfs(*it);
}

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

	int a, b;
	for (scanf ("%d %d\n", &N, &M); M; -- M){
		scanf ("%d %d\n", &a, &b); G[a].pb(b); G[b].pb(a);
	}

    for (int i = 1; i <= N; ++ i)
		if (!viz[i]) ++cnt, dfs(i);
	printf ("%d\n", cnt); 

	return 0;
}