Cod sursa(job #159153)

Utilizator nimeniaPaul Grigoras nimenia Data 13 martie 2008 23:20:55
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 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=p[nxd];
	while (aux){
	if (marc[aux->nd]==0) {
		printf("%ld ",aux->nd);
		dfs(aux->nd);
		marc[aux->nd]=1; nmarc++;
	 }aux=aux->urm;
	}
}

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;
	}


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



	 printf("%ld",n_con);

	return 0;
}