Pagini recente » Cod sursa (job #3120801) | Istoria paginii utilizator/45_45_45 | Cod sursa (job #1857462) | Istoria paginii runda/oji20091112/clasament | Cod sursa (job #2749873)
#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 100000
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int> adj[NMAX];
void dfs(int node, vector<int>& visited) {
visited[node] = 1;
for (auto child : adj[node])
dfs(child, visited);
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int node_in, node_out;
fin >> node_in >> node_out;
adj[node_in].push_back(node_out);
}
int nr_componente = 0;
vector<int> visited(n + 1, 0);
// find the starting position
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) {
dfs(i, visited);
nr_componente++;
}
}
fout << nr_componente;
}