POJ - 3352 Road Construction(邊雙連通分量)

題目大意：給出一張無向圖，問添加多少邊才能使得這張無向圖變成邊雙連通分量

解題思路：先求出所有的邊雙連通分量，再将邊雙連通縮成一個點，通過橋連接配接起來，這樣就形成了一棵無根樹了

現在的問題是，将這顆無根樹變成邊雙連通分量

網上的解釋是：統計出樹中度為1的節點的個數，即為葉節點的個數，記為leaf。則至少在樹上添加(leaf+1)/2條邊，就能使樹達到邊二連通，是以至少添加的邊數就是(leaf+1)/2。具體方法為，首先把兩個最近公共祖先最遠的兩個葉節點之間連接配接一條邊，這樣可以把這兩個點到祖先的路徑上所有點收縮到一起，因為一個形成的環一定是雙連通的。然後再找兩個最近公共祖先最遠的兩個葉節點，這樣一對一對找完，恰好是(leaf+1)/2次，把所有點收縮到了一起。

附上大神的詳解

和相關的連通分量的概念

#include <cstdio>
#include <cstring>

#define N 1010
#define min(a,b) ((a)<(b) ?(a):(b))

struct Edge{
    int to, next;
}E[N*];

int n, m, tot, dfs_clock, bcc_cnt, top, bnum;;
int head[N], pre[N], belong[N], degree[N], stack[N], bridge[N][];

void Addegreedge(int u, int v) {
    E[tot].to = v; E[tot].next = head[u]; head[u] = tot++;
    u = u ^ v; v = v ^ u; u = u ^ v;
    E[tot].to = v; E[tot].next = head[u]; head[u] = tot++;
}

void init() {
    memset(head, -, sizeof(head));
    tot = ;

    int u, v;
    for (int i = ; i < m; i++) {
        scanf("%d%d", &u, &v);
        Addegreedge(u, v);
    }
}

int dfs(int u, int fa) {
    int lowu = pre[u]  = ++dfs_clock;
    stack[++top] = u;
    for (int i = head[u]; i != -; i = E[i].next) {
        int v = E[i].to;

        if (!pre[v]) {
            int lowv = dfs(v, u);
            lowu = min(lowv, lowu);
            if (lowv > pre[u]) {
                bridge[bnum][] = u;
                bridge[bnum++][] = v;

                bcc_cnt++;
                while () {
                    int x = stack[top--];
                    belong[x] = bcc_cnt;
                    if (x == v) break;
                }
            }
        }else if (pre[v] < pre[u] && v != fa) {
            lowu = min(lowu, pre[v]);
        }   
    }
    return lowu;
}

void solve() {
    memset(degree, , sizeof(degree));
    memset(pre, , sizeof(pre));
    dfs_clock = bcc_cnt = top = bnum = ;
    dfs(, -);

    if (top) {
        bcc_cnt++;
        while () {
            int x = stack[top--];
            belong[x] = bcc_cnt;
            if (x == )
                break;
        }
    }

    for (int i = ; i < bnum; i++) {
        int u = bridge[i][];
        int v = bridge[i][];
        degree[belong[u]]++;
        degree[belong[v]]++;
    }

    int leaf = ;
    for (int i = ; i <= bcc_cnt; i++)
        if (degree[i] == )
            leaf++;
    printf("%d\n", (leaf + )/ );
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        solve();
    }
    return ;
}