Cod sursa(job #548410)

Utilizator bomboscristinabombos maria cristina bomboscristina Data 7 martie 2011 14:11:41
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream.h>
#define NM 101

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;
	 }