Cod sursa(job #548400)

Utilizator ShikaMonaVieriu Ramona ShikaMona Data 7 martie 2011 14:06:31
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream.h>
#define NM 100000
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 dfs(int x){
int y;
nod *nc=urm[x];
while(nc){ viz[x]=cc;
		   y=nc->nr;
		   nc=nc->next;
		   if(!viz[y]) dfs(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++;
							   dfs(i);
							   }
out<<cc;
return 0;
}