Cod sursa(job #359996)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 29 octombrie 2009 11:42:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<stdio.h>

#include<vector>

using namespace std;

vector <int> v[100005];
long n,k,viz[100005],nr,a,b;
void recur ( int poz)
{
	int i,q;
	if(viz[poz]==1)
		return;
	viz[poz]=1;
	q=v[poz].size();
	for(i=0;i<q;i++)
		if(viz[v[poz][i]]==0)
			recur(v[poz][i]);
}
int main ()
{		
		int i;
		freopen( "dfs.in" , "r" , stdin);
		freopen( "dfs.out" , "w" , stdout);
		scanf("%ld%ld",&n,&k);
		for(i=1;i<=k;i++)
		{
			scanf("%ld%ld",&a,&b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		for(i=1;i<=n;i++)
		{
			if(viz[i]==0)
			{
				nr++;
				recur(i);
			}
		}
		printf("%ld",nr);
		return 0;
}