#include #include #include #include using std::vector; using std::stack; void dfs(vector > &adj, vector &visited, stack &order, int v) { visited[v] = true; int s = adj[v].size(); for (int j = 0; j < s; j++) { int w = adj[v][j]; if (!visited[w]) dfs(adj, visited, order, w); } order.push(v); } void dfs(vector > &adj, vector &visited, int v) { visited[v] = true; int s = adj[v].size(); for (int j = 0; j < s; j++) { int w = adj[v][j]; if (!visited[w]) dfs(adj, visited, w); } } int number_of_strongly_connected_components(vector > adj) { int result = 0; vector > radj(adj.size(), vector()); for (size_t i = 0; i < adj.size(); i++) for (size_t j = 0; j < adj[i].size(); j++) radj[adj[i][j]].push_back(i); stack order; vector visited(radj.size(), 0); for (size_t i = 0; i < adj.size(); i++) if (!visited[i]) dfs(adj, visited, order, i); for (size_t i = 0; i < visited.size(); i++) visited[i] = false; while(!order.empty()) { int v = order.top(); order.pop(); if (!visited[v]) { result += 1; dfs(radj, visited, v); } } return result; } int main() { size_t n, m; std::cin >> n >> m; vector > adj(n, vector()); for (size_t i = 0; i < m; i++) { int x, y; std::cin >> x >> y; adj[x - 1].push_back(y - 1); } std::cout << number_of_strongly_connected_components(adj) << '\n'; }