Cod sursa(job #159159)

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


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


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

void dfs(long nxd)
{   nod *aux;
	marc[nxd]=1;nmarc++;
	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;
	}


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



	 printf("%ld",n_con);

	return 0;
}