Cod sursa(job #598792)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 27 iunie 2011 09:55:01
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
using namespace std;
long N,M,i,j,x,y,adiac[1001][1001],viz[1001],stiva[1001],total;

void parcurgere_dfs (long start)
{
	long p=1,u=1;
	int ok;
	stiva[1]=start;
	while (u)
	{
		viz[stiva[p]]=1;
		ok=0;
		for (i=1; i<=N && !ok; i++) if (!viz[i] && adiac[stiva[p]][i]) {stiva[++u]=i; ok++;}
		if (!ok) u--;
		p=u;
	}
	total++;
}

int main ()
{
	freopen("dfs.in", "r",stdin);
	scanf("%d %d", &N, &M);
	for (i=1; i<=M; i++)
	{
		scanf("%d %d", &x,&y);
		adiac[x][y]=adiac[y][x]=1;
	}
	freopen("dfs.out", "w",stdout);
	for (j=1; j<=N; j++) if (!viz[j]) parcurgere_dfs(j);
	printf("%d", total);
	return 0;
}