Pagini recente » Cod sursa (job #2074881) | Cod sursa (job #761415) | Cod sursa (job #2937095) | Cod sursa (job #168103) | Cod sursa (job #2679805)
#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;
}