Cod sursa(job #278358)

Utilizator alex3el_n2oAlex Vladescu alex3el_n2o Data 12 martie 2009 11:44:05
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#define nmax 100005
int use[nmax];
struct nod
{
	int varf;
	nod *adr;
} *q[nmax];

void add(long x, long y)
{
	nod *aux;
	aux=new nod;
	aux->varf=y;
	aux->adr=q[x];
	q[x]=aux;
}

void dfs(long a)
{
	nod *aux;
	aux=q[a];
	use[a]=1;
	while (aux!=NULL)
	{
		if (!use[aux->varf]) dfs(aux->varf);
		aux=aux->adr;
	}
}

int main()
{
	long nr=0,n,m,i,a,b;
	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);
		add(a,b);
	}
	for (i=1;i<=n;i++)
		if (!use[i]) {
			dfs(i);
			nr++;
		}
	printf("%ld\n",nr);
	return 0;
}