Cod sursa(job #335329)

Utilizator crisojogcristian ojog crisojog Data 29 iulie 2009 15:45:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 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]=cont;  
			dfs(p->nd);  
        }  
    }  
}
long x,y;
void ins()
{
	nod  *p,*q;
	p=new nod;  
	p->nd=y;
	p->next=L[x];
	L[x]=p;
	q=new nod;  
	q->nd=x;
	q->next=L[y];
	L[y]=q;
}
int main()
{	
	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);
		ins();		
	}
	for(i=1;i<=n;++i)
	{
		if(!viz[i])	
		{
			cont++;
			viz[i]=cont;
			dfs(i);
		}
	}
	printf("%ld\n",cont);
	return 0;
}