Cod sursa(job #493081)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 16 octombrie 2010 22:39:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>
#include<vector>

using namespace std;

const int Nmax = 100001;

vector <int> G[Nmax];
int N, M, sol;
char viz[Nmax];

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

int main() {
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	int i, j;
	
	scanf("%d %d",&N,&M);
	while(M--) {
		scanf("%d %d",&i,&j);
		G[i].push_back(j);
		G[j].push_back(i);
	}
	
	for(i=1; i<=N; i++) 
		if(!viz[i]) {
			dfs(i);
			sol++;
		}
	
	printf("%d\n",sol);
	
	return 0;
}