Cod sursa(job #755334)

Utilizator SmarandaMaria Pandele Smaranda Data 5 iunie 2012 14:43:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <long> a[100006];

long viz[100006];

void dfs (long x) {
	vector <long> :: iterator it;
	viz[x]=1;
	for (it=a[x].begin();it!=a[x].end();++it) 

		if (!viz[*it]) 
			dfs(*it);
}

int main () {
	long n,m,x,y,nr=0,i;
	
	freopen ("dfs.in","r",stdin);
	freopen ("dfs.out","w",stdout);
	
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;i++) {
		scanf("%ld%ld",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (i=1;i<=n;i++)
		if (!viz[i]) {
			dfs(i);
			nr++;
		}
	printf("%ld\n",nr);
	return 0;
}