Cod sursa(job #278530)

Utilizator paulDeac Adrian paul Data 12 martie 2009 13:09:49
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<stdio.h>

#define in "df.in"
#define out "df.out"

struct nod{
	long nd;
	nod *next;
}*l[100001],*p;

long n,m,x,y,i,s[100001],cont;

void df(int);

int main()
{
	freopen(in,"r",stdin);
	freopen(out,"w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%ld%ld",&x,&y);
		p=new nod;
		p->nd=y;
		p->next=l[x];
		l[x]=p;
		p=new nod;
		p->nd=x;
		p->next=l[y];
		l[y]=p;
	}
	for(i=1;i<=n;i++)
	{
		if(!s[i])
		{
			df(i);
			cont++;
		}
	}
	printf("%ld",cont);
	return 0;

}
void df(int nodd)
{
	s[nodd]=1;
	nod *q;
	q=l[nodd];
	while(q)
	{
		if(!s[q->nd])
		{
			df(q->nd);
		}
		q=q->next;
	}
}