Cod sursa(job #285035)

Utilizator adelinavVidovici Adelina adelinav Data 22 martie 2009 12:07:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
int n,m,stiva[100001],viz[100001],ncc;

struct nod{
	int info;
	nod *adr;
};

struct lista{
	nod *vf,*sf;
};

lista v[100001];
nod *uv[100001];

void addend(lista &l,int x){
	nod *n=new nod;
	n->info=x;
	n->adr=NULL;
	if(!l.vf) l.vf=n;
	else l.sf->adr=n;
	l.sf=n;
}

void dfs(int start){
	int k,up,x;
	k=1;
	stiva[k]=start;
	viz[start]=1;
	uv[k]=v[start].vf;
	while(k){
		up=0;
		while(!up&&uv[k]){
			x=uv[k]->info;
			if(!viz[x]){
				up=1;
			}
			uv[k]=uv[k]->adr;
		}
		if(up){
			k++;
			stiva[k]=x;
			viz[x]=1;
			uv[k]=v[x].vf;
		}
		else k--;
	}
}

int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,x,y;
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		addend(v[x],y);
		addend(v[y],x);
	}
	
	for(i=1;i<=n;i++)
		if(!viz[i]){
		ncc++;
		dfs(i);
		}
	printf("%d",ncc);
	return 0;
}