Cod sursa(job #159168)

Utilizator nimeniaPaul Grigoras nimenia Data 13 martie 2008 23:30:44
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 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;
	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;
	}

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