POJ 3177 Redundant Paths - 雙邊連通分量縮點 + 樹葉子數

問題描述

給定連通無向圖，需添加最少邊使其成為邊雙連通圖（即無橋）。輸出需加邊數。

理論基礎

將圖的邊雙連通分量縮點，形成一棵樹（橋樹）。樹中葉子節點數為 L，則至少需添加 ceil(L/2) = (L+1)/2 條邊使其無橋。

算法步驟

1. Tarjan 算法找橋（割邊）。
2. 去除橋後，DFS 縮點得到邊雙連通分量。
3. 橋連接的兩個分量在橋樹中度 +1。
4. 統計橋樹中度為 1 的節點數 L，答案 = (L+1)/2。

關鍵點：重邊處理

重邊不構成橋。Tarjan 時若不處理重邊，會誤判。兩種處理：

• 建圖前去重（用鄰接矩陣或 set）。
• Tarjan 中用邊索引區分，僅當該邊為橋且無其他平行邊時才計入度。

代碼實現（C++，用橋計算度）

#include 
using namespace std;
const int MAXN = 200005, MAXM = 2000005;
int n, m, dfn[MAXN], low[MAXN], stk[MAXN], top, idx, bccCnt;
bool isBridge[MAXM];
vector G[MAXN];
struct Edge { int to, id; };
vector adj[MAXN];

void tarjan(int u, int parentEdge) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    for (auto e : adj[u]) {
        int v = e.to, id = e.id;
        if (id == parentEdge) continue;
        if (!dfn[v]) {
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) isBridge[id] = true;
        } else low[u] = min(low[u], dfn[v]);
    }
}

void dfsBCC(int u, int bccId) {
    // 縮點邏輯
}

int main() {
    while (cin >> n >> m) {
        // 初始化、建圖、去重
        tarjan(1, -1);
        // 縮點、統計橋樹葉子
        cout << (leaf + 1) / 2 << '\n';
    }
}

完整代碼較長，核心為 Tarjan 找橋 + 縮點統計葉子。