Cod sursa(job #548432)

Utilizator iordacheinaiordache ina alexandra iordacheina Data 7 martie 2011 14:20:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream.h>
#define NM 100001

ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod{
			int nr;
			nod *next;
			};
nod *l[NM],*urm[NM];
int n,m,viz[NM],cc;

void add(nod *&l,int x){
nod *nn=new (nod);
nn->nr=x;
nn->next=l;
l=nn;
}

void build(){
int i,x,y;
fin>>n>>m;
for(i=0;i<m;i++){ fin>>x>>y;
add(l[x],y);
add(l[y],x);
}
}

void df(int x){
int y;
nod *nc=urm[x];
while(nc){ viz[x]=cc;
					y=nc->nr;
					nc=nc->next;
					if(!viz[y]) df(y);
					urm [x]=nc;

					}
}


int main(){
int i;
build();
for(i=1;i<=n;i++) urm[i]=l[i];
for(i=1;i<=n;i++)
	 if(!viz[i]){cc++;
							 df(i);
							 }
fout<<cc;
return 0;
}