【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)。