Cod sursa(job #2423194)

Utilizator dornexDorneanu Eduard-Gabriel dornex Data 20 mai 2019 21:47:23
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

void DFS(vector <int>& viz, vector < vector <int>>&V, int nod) {
	viz[nod] = 1;
	for (auto x : V[nod]) {
		if (viz[x] == 0)
			DFS(viz, V, x);
	}
}

int main() {
	int n, m;
	f >> n >> m;

	vector < vector<int>> V(n + 1);
	vector <int> viz(n + 1, 0);

	for (int i = 0; i < m; i++) {
		int x, y;
		f >> x >> y;
		V[x].push_back(y);
	}

	int nr_conexe = 0;
	for (int i = 1; i <= n; i++) {
		if (viz[i] == 0) {
			DFS(viz, V, i);
			nr_conexe++;
		}
	}

	g << nr_conexe << '\n';
	return 0;
}