/* * Author: nskybytskyi * Time: 2022-01-13 15:08:45 */ #include using namespace std; //https://cp-algorithms.com/graph/strongly-connected-components.html int main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; vector> adj(n), adj_rev(n); vector used; vector order, component; while (m--) { int a, b; cin >> a >> b; --a, --b; adj[a].push_back(b); adj_rev[b].push_back(a); } function dfs1 = [&] (int v) -> void { used[v] = true; for (auto u: adj[v]) if (!used[u]) dfs1(u); order.push_back(v); }; function dfs2 = [&] (int v) -> void { used[v] = true; component.push_back(v); for (auto u : adj_rev[v]) if (!used[u]) dfs2(u); }; used.assign(n, false); for (int i = 0; i < n; ++i) if (!used[i]) dfs1(i); used.assign(n, false); reverse(order.begin(), order.end()); vector roots(n, 0); vector root_nodes; for (auto v: order) if (!used[v]) { dfs2(v); int root = component.front(); for (auto u : component) roots[u] = root; root_nodes.push_back(root); component.clear(); } map scc_in, scc_out; for (int v = 0; v < n; ++v) { int root_v = roots[v]; scc_in[root_v] = scc_out[root_v] = 0; } for (int v = 0; v < n; v++) for (auto u : adj[v]) { int root_v = roots[v], root_u = roots[u]; if (root_u != root_v) { ++scc_out[root_v]; ++scc_in[root_u]; } } if (root_nodes.size() == 1) { cout << 0 << "\n"; } else { int cnt_in = 0, cnt_out = 0; for (auto [k, v] : scc_in) { if (!v) { ++cnt_in; } } for (auto [k, v] : scc_out) { if (!v) { ++cnt_out; } } cout << min(cnt_out, cnt_in) << "\n"; } return 0; }