Cod sursa(job #285946)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 23 martie 2009 11:20:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#define NM 100001

struct nod{
	int x;
	nod*next;
	};
struct lista{
	nod*vf,*sf;
	};
lista l[NM+1];

int n,m,viz[NM],s[NM];
nod* u[NM];
void addend(lista &l,int x){
nod *n=new nod;
n->x=x;
n->next=NULL;
if(!l.vf) l.vf=n;
else l.sf->next=n;
l.sf=n;
}

void dfs(int start){
int k,up,x;
k=1;s[k]=start;u[k]=l[start].vf;viz[start]=1;
while(k){
	up=0;
	while(!up&&u[k]){
		x=u[k]->x;
		if(!viz[x]) up=1;
        u[k]=u[k]->next;
		}
	if(up){
		k++;
		s[k]=x;
		u[k]=l[x].vf;
		viz[x]=1;
		}
	else k--;
	}
}



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