Cod sursa(job #335319)

Utilizator crisojogcristian ojog crisojog Data 29 iulie 2009 15:23:16
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
long n,m,cont,viz[100010],i;
struct nod
{
	int nd;
	nod *next;
}; nod *L[100010];
void dfs(long a)
{
	if (L[a]==NULL)  
    {  
		return;  
    }  
	nod *p;
	for (p=L[a];p!=NULL;p=p->next)  
    {  
		if (!viz[p->nd])  
        {  
			viz[p->nd]=1;  
			dfs(p->nd);  
        }  
    }  
}
int main()
{	
	nod  *p,*q;
	long x,y;
	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);
		if(x!=y)
		{
			p=new nod;  
			p->nd=y;
			p->next=L[x];
			L[x]=p;
			q=new nod;  
		    q->nd=i;
		    q->next=L[y];
		    L[y]=q;
		}
	}
	for(i=1;i<=n;++i)
	{
		if(!viz[i])	cont++,dfs(i);
	}
	printf("%ld\n",cont);
	return 0;
}