Cod sursa(job #146981)

Utilizator damaDamaschin Mihai dama Data 2 martie 2008 14:41:01
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <stdio.h>
#include <vector>

using namespace std;

int used[100010], n, m, sol;
vector<int> v[100010];

void dfs(int nod);

int main()
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	int i, a, b;

	scanf("%d %d", &n, &m);

	for(i = 1; i <= n; ++i)
	{
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}

	for(i = 1; i <= n; ++i)
	{
		if(!used[i])
		{
			++sol;
			dfs(i);
		}
	}
	printf("%d\n", sol);

	return 0;
}

void dfs(int nod)
{
	int i, sz = v[nod].size();
	used[nod] = 1;

	for(i = 0; i < sz; ++i)
	{
		if(!used[v[nod][i]])
		{
			dfs(v[nod][i]);
		}
	}
}