Cod sursa(job #146680)

Utilizator ProtomanAndrei Purice Protoman Data 1 martie 2008 23:34:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#define mx 2000010
struct nod
{
	long nr;
	nod *ua;
} *l[mx];
long i,n,m,ncc,a,b;
char s[mx];

void clad(int t, int f)
{
	nod *p;
	p=new nod;
	p->nr=f;
	p->ua=l[t];
	l[t]=p;
}

void dfs(int xa)
{
	nod *p;
	for (p=l[xa]; p; p=p->ua)
		if (s[p->nr]==0)
		{
			s[p->nr]=1;
			dfs(p->nr);
		}
}

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",&a,&b);
		clad(a,b);
		clad(b,a);
	}
	for (i=1; i<=n; i++)
		if (s[i]==0)
		{
			ncc++;
			dfs(i);
		}
	printf("%ld",ncc);
	fclose(stdin);
	fclose(stdout);
	return 0;
}