Cod sursa(job #960258)

Utilizator gabrieligabrieli gabrieli Data 10 iunie 2013 03:47:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

void dfs (int v, const vector <vector <int>> &G, vector <bool> &visited)
{
	visited[v] = true;	
	for (auto &u : G[v])
		if (!visited[u])
			dfs (u, G, visited);
}

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

	int N, m;
	fin >> N >> m;

	vector <vector <int>> G (N+1);
	vector <bool> visited (N+1, false);

	for (; m; --m)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	int nr = 0;
	for (int i = 1; i <= N; ++i)
		if (!visited[i])
		{
			++nr;
			dfs (i, G, visited);
		}

	fout << nr << endl;
	fout.close();
	return EXIT_SUCCESS;
}