Cod sursa(job #159184)

Utilizator nimeniaPaul Grigoras nimenia Data 13 martie 2008 23:37:29
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <stdio.h>


struct nod{
	 nod *urm;
	 long nd;
}*p[1000],*aux;


long n,m,i,x,y,marc[1000],nmarc,n_con;

void dfs(long nxd)
{   nod *aux;
	marc[nxd]=1;
	for(aux=p[nxd];aux!=NULL;aux=aux->urm)
		if (!marc[aux->nd]) dfs(aux->nd);
}

int main(){

	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%ld%ld", &n,&m);

	for(i=0;i<m;i++){
		scanf("%ld%ld",&x,&y);
		aux=new nod;
		aux->urm=p[x];
		aux->nd=y;
		p[x]=aux;
		aux=new nod;
		aux->urm=p[y];
		aux->nd=x;
		p[y]=aux;
	}

	long gasit=1;
	while(gasit){
		gasit=0;
		for(i=1;i<=n;i++) if (marc[i]==0) {gasit=1;break;}
		if (gasit){dfs(i);n_con++;}
	}



	 printf("%ld",n_con);

	return 0;
}