Cod sursa(job #188607)

Utilizator slayer4uVictor Popescu slayer4u Data 9 mai 2008 11:23:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>
#include <vector>
using namespace std;

vector <long> x[100001];
long i, num, n, a, b, m, visited[100001];

void dfs(long nod)
{
	visited[nod] = 1;
	for (long i = 0; i < x[nod].size(); ++i)
		if (!visited[x[nod][i]])
			dfs(x[nod][i]);
}

int main()
{
	freopen ("dfs.in", "rt", stdin);
	freopen ("dfs.out", "wt", stdout);

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

	num = 1;
	dfs(1);
	for (i = 2; i <= n; ++i)
		if (!visited[i])
			++num, dfs(i);

	printf("%ld\n", num);
	return 0;
}