分析

$\rm Tarjan$ 缩点将原图转化成 $\rm DAG$，统计每个强连通分量的出度入度，起点数量为 $src$，终点数量为 $des$。对于一个强连通分量，其中只要有一所学校获得新软件那么整个分量都能获得。

问题一

结论

只要把软件给所有起点即可，答案为起点个数 $src$。

证明

所有起点都无法由别的点到达，因此每个起点必须分配一个软件，而对于其他所有点，一定存在前驱，一定能由某一个起点走到，也就是说从所有起点出发，能遍历整个图。因此只需要给所有起点各一个软件即可。

问题二

结论

1. 若 $scc\_cnt = 1$（只有一个强连通分量），则不需要连新的边，答案为 $0$。
2. 若 $scc\_cnt > 1$，则答案为 $\max(src, des)$。

证明（yxc讲解总结）

结论 $1$ 正确性显然，下面证明结论 $2$。

设缩点后的 $\rm DAG$ 中，起点（入度为 $0$）的集合为 $P$，终点（出度为 $0$）的集合为 $Q$。分以下两种情况讨论：

1. $|P| \le |Q|$

   ① 若 $|P|=1$，则只有一个起点，并且这个起点能走到所有点，只要将每一个终点都向这个起点连一条边，那么对于图中任意一点，都可以到达所有点，新加的边数为 $|Q|$。

   ② 若 $|P| \ge 2$，则 $|Q| \ge |P| \ge 2$，此时至少存在 $2$ 个起点 $p_1,p_2$，$2$ 个终点 $q_1,q_2$，满足 $p_1$ 能走到 $q_1$，$p_2$ 能走到 $q_2$。（反证法：如果不存在两个起点能走到不同的终点，则所有的起点一定只能走到同一个终点，而终点至少有两个，发生矛盾，假设不成立）。如下图：

   

   那么我们可以从 $q_1$ 向 $p_2$ 新连一条边，那么此时起点和终点的个数都会减少一个（$p_2$ 不再是起点，$q_1$ 不再是终点），因此只要以这种方式，连接新边 $|P|-1$ 条，则 $|P^{’}|=1$，而 $|Q^{’}|=|Q|-(|P|-1)$，由 ① 得，当 $|P’|=1$ 时，需要再连 $|Q’|$ 条新边，那么总添加的新边数量为 $|P|-1+|Q|-(|P|-1)=|Q|$。

2. $|Q| \le |P|$

   与情况 $1$ 对称，此时答案为 $|P|$。

综上所述，$scc\_cnt>1$ 时，问题二的答案为 $\max(|P|, |Q|)$ 即 $\max(src, des)$。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = N * N;

int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], tt;
bool in_stk[N];
int id[N], sz[N], scc_cnt;
int din[N], dout[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++tt] = u, in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stk[tt--];
            in_stk[v] = false;
            id[v] = scc_cnt;
            sz[scc_cnt]++;
        } while (v != u);
    }
} 

int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) {
        int t;
        while (cin >> t, t) add(i, t);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) dout[a]++, din[b]++;
        }
    }
    int src = 0, des = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (!din[i]) src++;
        if (!dout[i]) des++;
    }
    printf("%d\n", src);
    if (scc_cnt == 1) puts("0");
    else printf("%d\n", max(src, des));
    return 0;
}