Cod sursa(job #179724)

Utilizator Iceman_ftgBurghelea Alex Iceman_ftg Data 16 aprilie 2008 11:50:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream.h>
#define N  100010
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod {long info; nod *urm;};
long viz[N],comp=0,n,m;
nod *graf[N],*q,*p;
void insert(int i1,int i2)
 {  
     nod *p;  
     p=new nod;  
     p->info=i1;  
     if(!graf[i2]){p->urm=0;graf[i2]=p;}  
     else{p->urm=graf[i2];graf[i2]=p;}  
     p=new nod;  
     p->info=i2;  
     if(!graf[i1]){p->urm=0;graf[i1]=p;}  
     else{p->urm=graf[i1];graf[i1]=p;}  
 }
void citire()
{
long x,y,i;
fin>>n>>m;
for(i=1;i<=m;i++)
	{
	fin>>x>>y;
    insert(x,y);
	}
for(i=1;i<=n;i++)
	viz[i]=0;
}
void DF(int k)
{
long indice;
viz[k]=comp;
nod *z;
z=graf[k];
while (z)
	{
    indice=z->info;
	if (!viz[indice])
		DF(indice);
	z=z->urm;
    }
}
int main()
{
citire();
long i;
for(i=1;i<=n;i++)
	if(!viz[i])
	{
	comp++;
	DF(i);
	}
fout<<comp;
return 0;
}