Pagini recente » Cod sursa (job #548831) | Cod sursa (job #2078494) | Cod sursa (job #2938843) | Cod sursa (job #1515943) | Cod sursa (job #2702776)
#include <fstream>
#include <vector>
using namespace std;
void dfs(int node, vector<bool> & visited, vector<vector<int>> & graph) {
visited[node - 1] = true;
for (int neighbor: graph[node - 1]) {
if (!visited[neighbor - 1]) {
dfs(neighbor, visited, graph);
}
}
}
int main() {
ifstream fin("dfs.in");
int n, m;
fin >> n >> m;
vector<vector<int>> graph(n);
for (int i = 0; i < m; i++) {
int node1, node2;
fin >> node1 >> node2;
graph[node1 - 1].push_back(node2);
}
fin.close();
vector<bool> visited(n, false);
int no_connected_components = 0;
for (int node = 1; node <= n; node++) {
if (!visited[node - 1]) {
dfs(node, visited, graph);
no_connected_components++;
}
}
ofstream fout("dfs.out");
fout << no_connected_components;
fout.close();
return 0;
}