Cod sursa(job #801352)

Utilizator Mihnea35Gall Mihnea Mihnea35 Data 24 octombrie 2012 00:29:16
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>

using namespace std ;

struct nod {int nr;nod *adr;} ;
nod *v[100001] ;
long n,m ;
int viz[100001] ;
ofstream g ;

nod *nou (int nr) {
	nod *aux=new nod ;
	aux->nr=nr ;
	aux->adr=NULL ;
	return aux ;
}
void adaugare (nod *&a,long nr) {
	nod *aux=nou(nr) ;
	aux->adr=a ;
	a=aux ;
}
void citire ()	{
	long x,y,i ;
	for (i=1;i<=n;i++) v[i]=NULL ;
	ifstream f ("dfs.in") ;
	f>>n>>m ;
	for (i=1;i<=m;i++) {
		f>>x>>y ;
		adaugare(v[x],y) ;
		adaugare(v[y],x) ;
	}
	f.close() ;
}
/*void afisare (nod *p) {
	while (p) {
		g<<p->nr<<' ' ;
		p=p->adr ;
	}
	g<<endl ;
}*/
void dislocare (nod *p)	{
	nod *aux ;
	while (p) {
		aux=p->adr ;
		delete p ;
		p=aux ;
	}
}

void dfs (int x) {
	int s[100001],vf ;
	s[1]=x;vf=1;viz[x]=1;
	while (vf>0) {
		while (v[s[vf]]) {
			if (viz[v[s[vf]]->nr]==0) {s[vf+1]=v[s[vf]]->nr;viz[v[s[vf]]->nr]=1;vf++;break;}
			v[s[vf]]=v[s[vf]]->adr ;
		}
		if (!v[s[vf]]) vf-- ;
	}
}
int main ()	{
	long i,nr=0 ;
	citire() ;
	for (i=1;i<=n;i++)
		if (viz[i]==0) {
			nr++ ;
			dfs(i) ;
		}
	g.open("gfs.out") ;
	g<<nr ;
	g.close() ;
	for (i=1;i<=n;i++) dislocare(v[i]) ;
return 0 ;
}