lessons/参考实现/02-强连通与双连通/POJ-2186.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    while (m--) { int u, v; cin >> u >> v; g[--u].push_back(--v); }
    vector<int> dfn(n), low(n), comp(n, -1), st;
    vector<bool> in_stack(n);
    int timer = 0, count = 0;
    auto dfs = [&](auto &&self, int u) -> void {
        dfn[u] = low[u] = ++timer; st.push_back(u); in_stack[u] = true;
        for (int v : g[u]) {
            if (!dfn[v]) self(self, v), low[u] = min(low[u], low[v]);
            else if (in_stack[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            while (true) {
                int v = st.back(); st.pop_back(); in_stack[v] = false; comp[v] = count;
                if (v == u) break;
            }
            ++count;
        }
    };
    for (int v = 0; v < n; ++v) if (!dfn[v]) dfs(dfs, v);
    vector<int> size(count), outdeg(count);
    for (int v = 0; v < n; ++v) ++size[comp[v]];
    for (int u = 0; u < n; ++u) for (int v : g[u]) if (comp[u] != comp[v]) {
        ++outdeg[comp[u]];
    }
    int sink = -1;
    for (int c = 0; c < count; ++c) if (outdeg[c] == 0) {
        if (sink != -1) { cout << "0\n"; return 0; }
        sink = c;
    }
    cout << size[sink] << '\n';
}