Cod sursa(job #147018)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 2 martie 2008 15:13:20
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream.h>

int v[101],coada[10000],v1[101],comp[101],componente;
int *c[101];
int j,i,n;
void dfs(int nod)
	{
	componente++;
	int p=1,u=1;
	comp[i]=componente;
	coada[p]=nod;
	while(p<=u)
		{
		for(int z=1;z<=v[coada[p]];z++)
			{
			if(comp[c[nod][z]]!=componente)
				{
				comp[c[nod][z]]=componente;
				u++;
				coada[u]=c[nod][z];
				}
			}
		p++;
		}
	}
int main()
{
ifstream in("dfs.in");
int x,y;
in>>n;
while(in>>x>>y)
	{
	v[x]++;
	v[y]++;
	}
in.close();
for(i=1;i<=n;i++)
	c[i]=new int(v[i]);

ifstream file("dfs.in");
file>>n;
while(file>>x>>y)
	{
	c[x][v1[x]+1]=y;
	v1[x]++;
	c[y][v1[y]+1]=x;
	v1[y]++;
	}
file.close();



for(i=1;i<=n;i++)
	if(v[i]==0) comp[i]=++componente;
	else if(comp[i]==0) dfs(i);
ofstream out("dfs.out");
out<<componente<<"\n";
//for(i=1;i<=n;i++) cout<<comp[i]<<" ";
/*for(i=1;i<=n;i++)
	{
	for(j=1;j<=v[i];j++)
		out<<c[i][j]<<" ";
	out<<"\n";
	}
*/
out.close();
return 0;
}