Cod sursa(job #548435)

Utilizator alex25Muscalu Alexandra alex25 Data 7 martie 2011 14:20:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream.h>
#define NM 100001
ifstream in("dfs.in");
ofstream out("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;
in>>n>>m;
for(i=1;i<=m;i++){ in>>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);
																}
out<<cc;
return 0;
}