Cod sursa(job #548403)

Utilizator lilianaBBatranca Liliana Ana-Maria lilianaB Data 7 martie 2011 14:07:14
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream.h>
#define NM 100
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;
}