Cod sursa(job #181320)

Utilizator hadesgamesTache Alexandru hadesgames Data 18 aprilie 2008 11:29:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>

int viz[100005],e[100005],n,m,nr;
typedef struct nod
{
	int x;
	nod *a;
} *pnod;
pnod a[100005];
void add(pnod &b,int x)
{
	pnod p;
	p=new nod;
	p->x=x;
	p->a=b;
	b=p;
}
void dfs(int x)
{
	pnod i;
	viz[x]=1;
	for (i=a[x];i!=NULL;i=i->a)
		if (!viz[i->x])
			dfs(i->x);
}
int main()
{
	int i,x,y;
	FILE *in,*out;
	in=fopen("dfs.in","r");
	out=fopen("dfs.out","w");
	fscanf(in,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(in,"%d%d",&x,&y);
		add(a[x],y);
		add(a[y],x);
	}
	for (i=1;i<=n;i++)
	{
		if (!viz[i])
		{
			nr++;
			dfs(i);
		}
		
	}
	fprintf(out,"%d",nr);
	fclose(in);
	fclose(out);
	return 0;

}