Cod sursa(job #548419)

Utilizator add_dragosAndrei Dragos add_dragos Data 7 martie 2011 14:15:53
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 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=0;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;
}