【ACWing】367. 学校网络

题目地址：

https://www.acwing.com/problem/content/369/

一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校 A A A支援学校 B B B，并不表示学校 B B B一定要支援学校 A A A）。当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。现在请问最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？最少需要添加几条新的支援关系，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

输入格式：

第 1 1 1行包含整数 N N N，表示学校数量。第 2... N + 1 2...N+1 2...N+1行，每行包含一个或多个整数，第 i + 1 i+1 i+1行表示学校 i i i应该支援的学校名单，每行最后都有一个 0 0 0表示名单结束（只有一个 0 0 0即表示该学校没有需要支援的学校）。

输出格式：

输出两个问题的结果，每个结果占一行。

数据范围：

2 ≤ N ≤ 100 2≤N≤100 2≤N≤100

可以把学校之间的支援关系看成一个图，那么此题即要问，至少选多少个点，就可以使得每个点都可以由这些点中的某一个走到。先对整个图求一遍强连通分量，然后缩点，容易想到只需要在每个入度为 0 0 0的强连通分量里各选一个点即可，并且确实不能选更少的点（否则的话必然有一个强连通分量里的点是到不了的）。接着还要求最少需要加多少条边，就可以使得整个图成为一个强连通分量。设缩点后的图里，有 p p p个入度为 0 0 0的点，有 q q q个出度为 0 0 0的点，结论是至少需要加 max ⁡ { p , q } \max\{p,q\} max{p,q}条边（注意如果 p = q = 1 p=q=1 p=q=1，则答案是 0 0 0，此时说明整个图已经是强连通图了）。

证明如下：不妨设 p ≥ q p\ge q p≥q（如果 p < q p<q p<q那么可以将图的每条边反个向即可）。如果 q = 1 q=1 q=1，那么将出度为 0 0 0的点连 p p p条边到 p p p个入度为 0 0 0的点，显然是一种方案，并且，如果只连少于 p p p条边，那么入度为 0 0 0的 p p p个点里必然有其中某个点没有入边，那么这个点将是到不了的，矛盾；如果 q > 1 q>1 q>1，则必然能找到 q q q个入度为 0 0 0的点，使得这些点逐个可以到达 q q q个出度为 0 0 0的点，且一一对应。如若不然，则说明 p p p个入度为 0 0 0的点都走不到某个出度为 0 0 0的点，这与缩点后的图是有向无环图矛盾。挑一个出度为 0 0 0的点 u u u和入度为 0 0 0的点 v v v，连一条边 u → v u\to v u→v，这就会把规模 ( p , q ) (p,q) (p,q)的问题转为规模 ( p − 1 , q − 1 ) (p-1,q-1) (p−1,q−1)的问题，后者的解是 max ⁡ { p , q } − 1 \max\{p,q\}-1 max{p,q}−1，所以原问题的解的上界就是 max ⁡ { p , q } = p \max\{p,q\}=p max{p,q}=p。如果解小于 p p p，同样会使得至少一个入度 0 0 0的点到不了，矛盾。

代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = 10010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[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[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], dfn[j]);
    }

    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do {
            y = stk[--top];
            in_stk[y] = false;
            id[y] = scc_cnt;
        } while (y != u);
    }
}

int main() {
    scanf("%d", &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 a = 0, b = 0;
    // 求一下缩点后的图里入度0和出度0的点各有多少个
    for (int i = 1; i <= scc_cnt; i++) {
        if (!din[i]) a++;
        if (!dout[i]) b++;
    }

    printf("%d\n", a);
    if (scc_cnt == 1) printf("0\n");
    else printf("%d\n", max(a, b));

    return 0;
}
           

时间复杂度 O ( n + m ) O(n+m) O(n+m)， n n n和 m m m分别是图的点数和边数，空间 O ( n ) O(n) O(n)。