Cod sursa(job #289084)

Utilizator spidyvenomMarius Toma spidyvenom Data 26 martie 2009 13:40:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream.h>
#define nmax 100001
int n,m,i,v[nmax],nr=0;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod
	{int z;
	nod *adr;};
nod *l[nmax];
void citire()
{
int i,j;
nod *c;
for (i=1;i<=m;i++) l[i]=NULL;
while (f>>i>>j)
	{
	c=new nod; c->z=j; c->adr=l[i]; l[i]=c;
	c=new nod; c->z=i; c->adr=l[j]; l[j]=c;
	}
}
void dfs(int x)
{
nod *c;
v[x]=1;
c=l[x];
while(c)
  {
  if(v[c->z]==0) dfs(c->z);
  c=c->adr;
  }
}
int main()
{
nod *c;
f>>n>>m;
citire();
/*for (i=1;i<=m;i++)
	{cout<<"L"<<i<<":";
	c=l[i];
	while(c) {cout<<c->z<<" ";
				c=c->adr;}
	cout<<'\n';
	} */
for (i=1;i<=n;i++)
	if (!v[i]) {nr++;dfs(i);}
g<<nr;
g.close();
return 0;
}