UVA 10972 RevolC FaeLoN：雙連通分量 + 孤立點處理 (縮點 + 度數統計)

問題描述

給定無向圖 (可能不連通，含孤立點)，求最少添加多少條邊使圖變為 雙邊連通 (即無橋，任意兩點間至少有兩條不相交路徑)。

核心思路：Tarjan 找橋 → 縮點 → 統計葉子數

1. 運行 Tarjan 算法找所有橋 (Low[v] > DFN[u])。
2. 將無橋邊縮點：同一雙連通分量賦予同一 Low 值 (或用 DFS 染色)。
3. 構建橋樹：每個分量為節點，橋為邊。孤立點單獨成分量，度為 0。
4. 統計橋樹中度為 0 的分量數 u (孤立點)，度為 1 的分量數 v (葉子)。
5. 答案 = (2*u + v + 1) / 2 (向上取整)。

孤立點特殊處理

孤立點在 Tarjan 中 head[u]==-1，不會被訪問到。需單獨標記其所在分量 used[Low[u]]=1，並計入度為 0 的計數。公式自然涵蓋：孤立點需加 2 條邊 (自成環或連兩條到別處)，度 1 葉子需加 1 條，配對後向上取整。

關鍵代碼片段

void Tarjan(int u, int pre) {
    Low[u] = DFN[u] = ++Index;
    for (int i=head[u]; ~i; i=edge[i].next) {
        int v = edge[i].to;
        if (v == pre) continue;
        if (!DFN[v]) {
            Tarjan(v, u);
            Low[u] = min(Low[u], Low[v]);
            if (Low[v] > DFN[u]) bridge++;
        } else Low[u] = min(Low[u], DFN[v]);
    }
}

void solve(int N) {
    // 1. 找橋
    for (int i=1;i<=N;i++) if (!DFN[i]) { Tarjan(i,i); bridge++; }
    if (bridge == 1) { puts("0"); return; } // 單點或已雙連通

    // 2. 縮點統計度
    memset(used,0,sizeof used); memset(dg,0,sizeof dg);
    for (int u=1; u<=N; u++) {
        if (head[u]==-1) { used[Low[u]]=1; continue; } // 孤立點
        for (int i=head[u]; ~i; i=edge[i].next) {
            int v = edge[i].to;
            used[Low[u]] = used[Low[v]] = 1;
            if (Low[u] != Low[v]) dg[Low[u]]++;
        }
    }
    int ans = 0;
    for (int i=1;i<=N;i++) {
        if (used[i] && dg[i]==0) ans += 2;
        else if (dg[i]==1) ans++;
    }
    printf("%d\n", (ans+1)/2);
}

複雜度

O(V+E)，V ≤ 1000，E ≤ 10^5，極快。