Cod sursa(job #718855)

Utilizator BeniLehelBeni Lehel BeniLehel Data 21 martie 2012 10:26:01
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
long long n,m;
long long l[100002]={0};
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	scanf("%lld%lld",&n,&m);
	long k=1;

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

		if(l[a]&&l[b])
		{
			if(l[a]<l[b])
			{
				for(int i=1;i<=n;i++)
					if(l[i]==l[b]&& i!=b)
						l[i]=l[a];
				l[b]=l[a];
			}
			else
			{
				for(int i=1;i<=n;i++)
					if(l[i]==l[a]&& i!=a)
						l[i]=l[b];
				l[a]=l[b];
			}
		}
		else
		if(l[a]||l[b])
		{
			if(l[a])
				l[b]=l[a];
			else
				l[a]=l[b];
		}
		else
		{
			l[a]=k;
			l[b]=k;
			k++;
		}
	}
	for(int i=1;i<=n;i++)
		if(!l[i])
		{
			l[i]=k;
			k++;
		}

	printf("%lld",k-1);
	return 0;
}