Cod sursa(job #772809)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 30 iulie 2012 22:57:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int> A[100001];
int ok[100001];
long N,M,i,j,k,total;

void dfs (int crt)
{
	int i,k=A[crt].size();
	for (i=0; i<k; i++)
		if (!ok[A[crt][i]])
		{
			ok[A[crt][i]]=1;
			dfs(A[crt][i]);
		}
}

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", &j, &k);
		A[j].push_back(k);
		A[k].push_back(j);
	}
	
	for (i=1; i<=N; i++)
		if (!ok[i]) total++, dfs(i);
	printf("%d\n", total);
	
	fclose(stdin); fclose(stdout);
	return 0;
}