Cod sursa(job #585319)

Utilizator valentina506Moraru Valentina valentina506 Data 28 aprilie 2011 21:25:56
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>
using namespace std;
ofstream g("dfs.out");
int n,m,i,j,*a[200001],x,y,p,q,ok;
int viz[101];
void df(int x)
{
	//g<<x<<" ";
	viz[x]=1;
	for(int i=1;i<=a[x][0];i++)
		if(!viz[a[x][i]])
			df(a[x][i]);
}

int main()
{
	ifstream f("dfs.in");
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		a[i]=(int *) realloc (a[i],sizeof(int));
	    a[i][0]=0;
	}
	while(f>>x>>y)
	{
		a[x][0]++;
		a[x]=(int *) realloc (a[x],(a[x][0]+1)*sizeof(int));
		a[x][a[x][0]]=y;
		a[y][0]++;
		a[y]=(int *) realloc (a[y],(a[y][0]+1)*sizeof(int));
		a[y][a[y][0]]=x;
	}
	ok=0;
	for(j=1;j<=n;j++)
		if(!viz[j])
		{
			ok++;
			df(j);
		}
		g<<ok;
	return 0;
}