Cod sursa(job #287970)

Utilizator hazegirlCatalina Predoi hazegirl Data 25 martie 2009 13:34:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
//dfs
#include<fstream.h>
#include<stdlib.h>
long int *A[100001];
long n,i,j,m,nrc,a,b;
int viz[100001];

void dfs(int x)
{viz[x]=1;
for(int j=1;j<=A[x][0];++j)
	if(!viz[A[x][j]])
		dfs(A[x][j]);
}

int main()
{ifstream f("dfs.in");
ofstream g("dfs.out");
f>>n>>m;
for(i=1;i<=n;++i)
	{A[i]=(long int *) calloc(1,sizeof(long int));
	A[i][0];
	}
for(i=1;i<=m;++i)
	{f>>a>>b;
	 A[a]=(long int *)realloc(A[a], (A[a][0]+2)*sizeof(long int));
	 A[a][++A[a][0]]=b;
	 A[b]=(long int *) realloc(A[b], (A[b][0]+2)*sizeof(long int));
	 A[b][++A[b][0]]=a;
	}


for(i=1;i<=n;i++)
	if(!viz[i])
		{dfs(i);
		nrc++;
		}
g<<nrc<<'\n';
f.close();
g.close();
return 0;

}