Cod sursa(job #953957)

Utilizator gabrieligabrieli gabrieli Data 27 mai 2013 21:03:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
/*
 * Algoritm pentru a determina numarul componentelor conexe ale unui graf
 * neorientat.
 *
 * Idee: DFS
 */
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

void dfs (int v, const vector <vector <int>> &G, vector <bool> &seen)
{
	seen[v] = true;
	for (size_t i = 0; i < G[v].size(); ++i)
		if (!seen[G[v][i]])
		{
			dfs (G[v][i], G, seen);
		}
}

int main()
{
	ifstream fin ("dfs.in");
	ofstream fout ("dfs.out");
	int n, m;

	fin >> n >> m;

	vector <vector <int>> G (n+1);
	for (; m; --m)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back (y);
		G[y].push_back (x);
	}

	int components (0);
	vector <bool> seen (n+1, false);
	for (int v = 1; v <= n; ++v) 
		if (!seen[v])
		{
			dfs (v, G, seen);
			++components;
		}

	fout << components << endl;

	fin.close();
	fout.close();
	return EXIT_SUCCESS;
}