A1602 消息扩散2

// A1602 消息扩散2 —— 强连通分量缩点
//
// 子任务 A：至少在几个城市发布消息，才能让所有城市都收到消息。
//   缩点后，入度为 0 的强连通分量（源分量）里必须各发一条消息，
//   其余分量都能从某个源分量到达，所以答案 = 源分量个数。
//
// 子任务 B：最少再加几条边（扩展），使任意城市发出的消息都能传到所有城市，
//   即把缩点后的图变成强连通。
//   若本来只有一个强连通分量，答案是 0；
//   否则答案 = max(源分量个数, 汇分量个数)。
//
// 「扩展」即在某个城市的可到达列表里加入一个新成员，也就是加一条边。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i <= n; i++) {
        int v;
        while (cin >> v && v != 0) g[i].push_back(v);
    }

    // Tarjan 求强连通分量
    vector<int> dfn(n + 1, 0), low(n + 1, 0), bel(n + 1, 0), stk;
    vector<char> inStk(n + 1, 0);
    int timer = 0, sccCnt = 0;
    function<void(int)> tarjan = [&](int u) {
        dfn[u] = low[u] = ++timer;
        stk.push_back(u);
        inStk[u] = 1;
        for (int v : g[u]) {
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (inStk[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (low[u] == dfn[u]) {
            sccCnt++;
            while (true) {
                int x = stk.back();
                stk.pop_back();
                inStk[x] = 0;
                bel[x] = sccCnt;
                if (x == u) break;
            }
        }
    };
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    // 缩点后各分量的入度与出度
    vector<int> indeg(sccCnt + 1, 0), outdeg(sccCnt + 1, 0);
    for (int u = 1; u <= n; u++) {
        for (int v : g[u]) {
            if (bel[u] != bel[v]) {
                outdeg[bel[u]]++;
                indeg[bel[v]]++;
            }
        }
    }
    int src = 0, sink = 0;
    for (int c = 1; c <= sccCnt; c++) {
        if (indeg[c] == 0) src++;
        if (outdeg[c] == 0) sink++;
    }

    cout << src << '\n';
    if (sccCnt == 1) {
        cout << 0 << '\n';
    } else {
        cout << max(src, sink) << '\n';
    }
    return 0;
}