Cod sursa(job #598994)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 27 iunie 2011 18:21:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <vector>

using namespace std;
long N,M,i,j,x,y,viz[100001],stiva[100001],G[100001],total;
vector <int> A[100001];

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=0; i<G[stiva[p]] && !ok; i++) if (!viz[A[stiva[p]][i]]) {stiva[++u]=A[stiva[p]][i]; ok++;}
		if (!ok) u--;
		p=u;
	}
	total++;
}

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