Cod sursa(job #1130596)

Utilizator axnsanCristi Vijdea axnsan Data 28 februarie 2014 14:14:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#ifdef __INFOARENA_PROJ
#include "infoarena.h"
#endif

#include <fstream>
#include <vector>
#include <queue>

#ifdef __INFOARENA_PROJ
namespace dfs {
#endif

unsigned const int maxN = 100000;

std::vector<unsigned> G[maxN + 1];
bool viz[maxN + 1];
void DFS(unsigned start)
{
	if (viz[start])
		return;

	viz[start] = true;
	for (std::vector<unsigned>::iterator it = G[start].begin(); it != G[start].end(); ++it)
		DFS(*it);
}

int main()
{
	std::ifstream in("dfs.in");
	std::ofstream out("dfs.out");
	unsigned N, M;
	in >> N >> M;
	for (unsigned i = 1; i <= M; ++i)
	{
		unsigned x, y;
		in >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	unsigned nCC = 0;
	for (unsigned i = 1; i <= N; ++i)
		if (!viz[i])
			++nCC, DFS(i);

	out << nCC << '\n';
	return 0;
}

#ifdef __INFOARENA_PROJ
}
#endif