AcWing 367. 学校网络

题目传送门

一、题目分析

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

问题一
结论:只要把软件给所有起点即可，答案为起点个数 \(src\)。

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

问题二
结论:若 scc_cnt=1（只有一个强连通分量），则不需要连新的边，答案为 \(0\)。
若 scc_cnt>1，则答案为 \(max(src,des)\)。

证明（\(yxc\)讲解总结）
结论 \(1\) 正确性显然，下面证明结论 \(2\)。

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

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

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

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

\(|Q|≤|P|\)
与情况 \(1\) 对称，此时答案为 \(|P|\)。

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

二、实现代码

#include 
using namespace std;

const int N = 110, M = 10010;

int n;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;
int din[N], dout[N];

//邻接表
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// Tarjan算法求强连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = 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], low[j]);
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int x;
        do {
            x = stk[top--];
            in_stk[x] = false;
            id[x] = scc_cnt;
        } while (x != 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 != -1; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) {
                dout[a]++;
                din[b]++;
            }
        }

    int a = 0, b = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (!din[i]) a++;  //入度为0的强连通块
        if (!dout[i]) b++; //出度为0的强连通块
    }

    printf("%d\n", a);
    if (scc_cnt == 1) //如果只有一个强连通块，不用连边
        puts("0");
    else
        printf("%d\n", max(a, b)); //输出入度为0与出度为0的连通块最大值
    return 0;
}