Cod sursa(job #326000)

Utilizator crisojogcristian ojog crisojog Data 23 iunie 2009 12:44:54
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.49 kb
#include<stdio.h>
long n,m,i,j,x,y,aux,l[100010],viz[100010],cont;
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;++i) l[i]=i;
	for(i=1;i<=m;++i)
	{
		scanf("%ld%ld",&x,&y);
		if(l[x]!=l[y])
		{
			if(x>y) 
			{
				aux=x;x=y;y=aux;
			}
			for(j=1;j<=n;++j)
				if(l[j]==y) l[j]=x;
		}
	}
	for(i=1;i<=n;++i)
		if(l[i]) viz[l[i]]=1;
	for(i=1;i<=n;++i) 
		if(viz[i]) cont++;
	printf("%ld\n",cont);
	return 0;
}