Redundant Paths

如何添加边使一个无向图变为边双连通分量。
双连通分量分为便双连通和点双连通。分别对应着桥和割点
这里我们解决的是便双连通分量。
正确的做法是，缩点。用桥连接。这样最后会变成一棵树。
那么最小的代价将这棵树变成一个便双连通分量就是连接其叶子节点成为一个环
及(leaves+1)/2 注意根也可能是叶子，所以还是统计度数为好

比较坑的是，这里面会有重边。故我们在判断桥时，要稍微改改。
具体见代码，就是记录边的编号。

代码如下

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int max_n = 5e3 + 100;
const int max_m = 1e4 + 100;
struct edge {
    int to, rev, next;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to, int rev) {
    E[cnt].to = to;E[cnt].rev = rev;
    E[cnt].next = head[from];
    head[from] = cnt++;
}
int dfn[max_n], low[max_n];
int tot = 0;
bool is[max_m];
void tarjan(int u, int fa_id) {
    dfn[u] = low[u] = ++tot;
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (i == fa_id)continue;
        if (!dfn[v]) {
            tarjan(v, E[i].rev);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                is[i] = is[E[i].rev] = true;
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

int color[max_n];
void draw(int u,int c) {
    color[u] = c;
    for (int i = head[u];i;i = E[i].next)
        if (color[E[i].to] == 0 && !is[i])
            draw(E[i].to, c);
}
int cct[max_n];
int F, R;
int main() {
    scanf("%d %d", &F, &R);
    for (int i = 1, u, v;i <= R;++i) {
        scanf("%d %d", &u, &v);
        add(u, v, cnt + 1);add(v, u, cnt - 1);
    }tarjan(1, 0);
    int tot = 0;
    for (int i = 1;i <= F;++i)
        if (color[i] == 0)
            draw(i, ++tot);
    for (int u = 1;u <= F;++u) {
        for (int i = head[u];i;i = E[i].next) {
            if (!is[i])continue;
            ++cct[color[u]];
            ++cct[color[E[i].to]];
        }
    }int ans = 0;
    for (int i = 1;i <= tot;++i)
        if (cct[i] == 2)
            ++ans;
    printf("%d\n", (ans + 1) / 2);
}