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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int u = 0; u < n; ++u) {
        int v;
        while (cin >> v && v != 0) g[u].push_back(v - 1);
    }
    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);
    if (count == 1) {
        cout << "1\n0\n";
        return 0;
    }
    vector<int> indeg(count), outdeg(count);
    for (int u = 0; u < n; ++u) for (int v : g[u]) if (comp[u] != comp[v]) {
        ++outdeg[comp[u]]; ++indeg[comp[v]];
    }
    int sources = 0, sinks = 0;
    for (int c = 0; c < count; ++c) {
        sources += indeg[c] == 0;
        sinks += outdeg[c] == 0;
    }
    cout << sources << '\n' << max(sources, sinks) << '\n';
}