Cod sursa(job #181303)

Utilizator hadesgamesTache Alexandru hadesgames Data 18 aprilie 2008 11:12:40
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
int *a[100005],viz[10],e[100005],n,m,nr;
void dfs(int x)
{
	int i;
	viz[x]=1;
	for (i=1;i<=a[x][0];i++)
		if (!viz[a[x][i]])
			dfs(a[x][i]);
}
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);
		e[x]++;
		e[y]++;
	}
	fclose(in);
	in=fopen("dfs.in","r");
	out=fopen("dfs.out","w");
	a[0]=new int[1];
	for (i=1;i<=n;i++)
	{
		a[i]=new int[e[i]+1];
	}
	for (i=1;i<=m;i++)
	{
		fscanf(in,"%d%d",&x,&y);
		a[x][0]++;
		a[y][0]++;
		a[x][a[x][0]]=y;
		a[y][a[y][0]]=x;
	}
	while (1);
	for (i=1;i<=n;i++)
	{
		if (!viz[i])
		{
			nr++;
			dfs(i);
		}
		
	}
	fprintf(out,"%d",nr);
	fclose(in);
	fclose(out);
	return 0;

}