Cod sursa(job #718995)

Utilizator BeniLehelBeni Lehel BeniLehel Data 21 martie 2012 12:13:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
long long n,m,k=0;
long long la[100001]={0};
vector <long long> l[100001];
//vector <long long>::iterator it;
void deep(long x);
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	scanf("%lld%lld",&n,&m);

	for(long long i=0;i<m;i++)
	{
		long long a,b;
		scanf("%lld%lld",&a,&b);

		l[a].push_back(b);

		l[b].push_back(a);

	}
	k=1;
	for(long long i=1;i<=n;i++)
		if(!la[i])
		{
			la[i]=k;
			deep(i);
			k++;
		}
	printf("%lld",k-1);

	return 0;
}
void deep(long x)
{
	vector <long long>::iterator it;
	it=l[x].begin();
	while(it != l[x].end())
	{
		if(!la[*it])
		{
			la[*it]=k;
			deep(*it);
		}
		++it;
	}
}