Cod sursa(job #370074)

Utilizator worstbyteelev gigel worstbyte Data 30 noiembrie 2009 04:45:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
using namespace std;
#define endl '\n'
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m,cc,viz[100001],st[100001];
struct nod{
	int inf;
	nod *adr;
};
struct lista{
	nod *vf,*sf;
};
lista v[100001];
nod *uv[100001]; 
void add(lista &l,int x){
	nod *n=new nod;
	n->inf=x;
	n->adr=NULL;
	if(!l.vf) l.vf=n;
	else l.sf->adr=n;
	l.sf=n;
}

void dfs(int start){
	int k=1,up;
	nod *nc;
	st[k]=start;
	viz[st[k]]=cc;
	nc=v[start].vf;
	while(nc&&viz[nc->inf]) nc=nc->adr;
	if(nc) uv[1]=nc;
	else return;
	while(k){
		up=0;
		while(!up&&nc){
			nc=uv[k];
			while(nc&&viz[nc->inf]) nc=nc->adr;
			if(nc) up=1;
		}
		if(up){
			uv[k]=nc;
			v[st[k]].vf=nc;
			k++;
		    st[k]=nc->inf;
		    viz[nc->inf]=cc;
		    uv[k]=v[nc->inf].vf;
		}
	    else {
			k--;
			nc=uv[k];
		}	
	}
}
int main(){
	fin>>n>>m;
	int i,x,y;
	for(i=1;i<=m;i++){
		fin>>x>>y;
		add(v[x],y);
		add(v[y],x);
	}
	for(i=1;i<=n;i++)
		if(!viz[i]){
			cc++;
			dfs(i);
		}
	fout<<cc;
	return 0;
}