Cod sursa(job #159088)

Utilizator nimeniaPaul Grigoras nimenia Data 13 martie 2008 22:45:54
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>


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


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

void dfs(long nxd)
{   nod *aux=p[nxd];
	while (aux){
	while(aux) {if (!marc[aux->nd]) break; aux=aux->urm;}
	if (aux!=NULL) {
		marc[aux->nd]=1; nmarc++;
		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;
	}


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


 /*	for(i=1;i<=n;i++){
		printf("%ld ",i);
		aux=p[i];
		while (aux)
			{printf("%ld ",aux->nd), aux=aux->urm;}
		printf("\n");

	}

		  */


	return 0;
}