Cod sursa(job #2679805)

Utilizator IoanaNadIoana Nadia Puiu IoanaNad Data 1 decembrie 2020 16:34:24
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>

void DFS(std::vector<std::vector<int>>& arches, std::vector<int>& visited, int node) {
	int length = arches[node - 1].size();
	for(int i = 1; i < length; ++i)
		if (visited[arches[node - 1][i] - 1] == 0) {
			visited[arches[node - 1][i] - 1] = 1;
			DFS(arches, visited, arches[node - 1][i]);
		}
}

int main() {
	std::ifstream fin("dfs.in");
	std::ofstream fout("dfs.out");
	int N, M;
	fin >> N >> M;
	std::vector<std::vector<int>> arches(N, std::vector<int>(1, 0));
	std::vector<int> visited(N, 0);
	int x, y;
	for (int i = 0; i < M; ++i) {
		fin >> x >> y;
		arches[x - 1].push_back(y);
	}
	int numberComponents = 0;
	for (int i = 0; i < N; ++i) {
		if (visited[i] == 0) {
			++numberComponents;
			DFS(arches, visited, i + 1);
		}
	}
	fout << numberComponents;
	return 0;
}