Cod sursa(job #2036495)

Utilizator robuvedVictor Robu robuved Data 10 octombrie 2017 19:13:16
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

void DFS(vector<vector<int>> G, int node, vector<bool>& visited)
{
	visited[node] = true;
	for (auto it = G[node].begin(); it != G[node].end(); it++)
	{
		if (!visited[*it])
			DFS(G, *it, visited);
	}
}
int main()
{
	int N, M;
	in >> N >> M;
	vector<vector<int>> G(N, vector<int>());
	for (int i = 0; i < M; i++)
	{
		int u, v;
		in >> u >> v;
		u--; v--;
		G[u].push_back(v);
	}
	vector<bool> visited(N, false);
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		if (!visited[i])
		{
			count++;
			DFS(G, i, visited);
		}
	}
	out << count;
}