HDU 4612：無向圖添加一條邊使橋最少 - 縮點 + 樹直徑

HDU 4612：無向圖添加一條邊使橋最少 - 縮點 + 樹直徑

無向圖中任意添加一條邊，使得橋（割邊）數量最少。含重邊（重邊構成邊雙連通分量）。

解題思路

1. 縮點：求邊雙連通分量（橋連接的塊），縮成樹。樹的邊即原圖的橋。
2. 求樹直徑：在樹上任選點 BFS 到最遠點 u，再從 u BFS 到最遠點 v，距離即直徑長度。
3. 答案 = 樹邊數 - 直徑長度。添加連接直徑兩端點的邊，可消除直徑上所有橋，剩餘橋最少。

Tarjan 求邊雙連通（無向圖）

用前向星存邊，標記訪問過的邊（雙向同時標記）。重邊自然在同一分量。關鍵：不使用 father 判斷，改用邊訪問標記。

struct Edge { int to, next; } e[2000500];
int head[300010], ecnt;
bool vis_edge[2000500];
int dfn[300010], low[300010], timer;
int stk[300010], top, scc[300010], scc_cnt;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;
    for (int i=head[u]; i!=-1; i=e[i].next) {
        if (vis_edge[i]) continue;
        int v = e[i].to;
        vis_edge[i] = vis_edge[i^1] = true; // 標記雙向
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stk[top--];
            scc[v] = scc_cnt;
        } while (v != u);
    }
}

重建樹 + 求直徑

int head2[300010], ecnt2;
int lev[300010];

void add_edge2(int u, int v) { ... } // 重建樹

void bfs(int s) {
    memset(lev, 0, sizeof(lev));
    queue q; q.push(s); lev[s]=1;
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (int i=head2[u]; i!=-1; i=e2[i].next) {
            int v=e2[i].to;
            if (!lev[v]) { lev[v]=lev[u]+1; q.push(v); }
        }
    }
}

int main() {
    while (scanf("%d%d", &n, &m) == 2 && (n||m)) {
        // 初始化、讀邊、建原圖
        tarjan(1);
        // 重建樹：遍歷原圖邊，不同 scc 連邊
        for (int u=1; u<=n; u++)
            for (int i=head[u]; i!=-1; i=e[i].next) {
                int v=e[i].to;
                if (scc[u] != scc[v]) add_edge2(scc[u], scc[v]);
            }
        bfs(1);
        int u = max_element(lev+1, lev+scc_cnt+1) - lev;
        bfs(u);
        int diam = *max_element(lev+1, lev+scc_cnt+1) - 1;
        printf("%d\n", scc_cnt - 1 - diam);
    }
}

關鍵點

1. 邊雙連通縮點：橋變為樹邊，塊變為樹節點。
2. 樹直徑：兩次 BFS，第一次任意點找最遠點（必為直徑一端），第二次從該端點找最遠距離。
3. 重邊處理：前向星 + 邊訪問標記天然支持，重邊不成橋，同屬一分量。
4. 棧溢出：遞歸深度可能達 3e5，需增棧或改迭代（代碼用 #pragma comment(linker, "/STACK:...")）。

複雜度

• Tarjan O(V+E)，BFS O(V)，總線性。

此題融合了「邊雙連通縮點」「樹直徑」「橋優化」三大圖論核心概念，是進階圖論的綜合訓練佳作。