解题思路

本题要求将给定的连通无向图转化为双连通图（任意两点间至少存在两条不共享边的路径），求需要添加的最少边数。关键在于利用图的边双连通分量性质：

1. 边双连通分量：删除所有桥后，图中每个连通块称为边双连通分量，内部无桥，任意两点间至少有两条边不相交的路径。
2. 缩点：将每个边双连通分量缩成一个点，原图转化为以桥为边的树结构（称为块树）。
3. 叶子节点：块树中的叶子节点（度数为1的节点）对应原图中的“需要连接”的分量。设叶子节点数为 leaf，则最少需要添加的边数为 (leaf + 1) / 2。

实现步骤

1. 找桥：使用 Tarjan 算法找出图中所有桥，确定边双连通分量。
2. 缩点构建块树：将每个边双连通分量缩成一个点，统计每个缩点的度数（即该分量在块树中的边数）。
3. 统计叶子节点：度数为1的缩点即为块树中的叶子节点，计算所需添加的边数。

代码解析

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 5005, M = 20005; // 边数开两倍处理无向图
int n, m;
struct Edge {
    int u, v, next;
} e[M << 1]; // 邻接表存储边
int head[N], tot; // 邻接表指针
int dfn[N], low[N], T; // Tarjan算法用到的时间戳和low值
int f[N]; // 并查集，用于缩点
int cut[N]; // 标记桥的另一端点（非必需，此处用于辅助判断）
int num[N]; // 缩点后每个分量的编号
int d[N]; // 缩点后每个分量的度数

// 初始化邻接表
void init() {
    tot = T = 0;
    memset(head, -1, sizeof(head));
    memset(dfn, 0, sizeof(dfn));
    for (int i = 1; i <= n; i++) f[i] = i; // 并查集初始化
}

// 并查集查找
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

// 合并集合
void Union(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) f[fx] = fy;
}

// Tarjan算法找桥，同时合并边双连通分量
void Tarjan(int u, int pre) {
    dfn[u] = low[u] = ++T;
    for (int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == pre) continue; // 跳过父节点
        if (!dfn[v]) { // 未访问过的节点
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) { // 发现桥，不合并u和v
                cut[v] = 1; // 标记桥的另一端点（非必需）
            } else { // 非桥边，合并u和v所在的边双连通分量
                Union(u, v);
            }
        } else { // 回边，更新low值
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        // 无向图添加两条边
        e[tot] = {u, v, head[u]}; head[u] = tot++;
        e[tot] = {v, u, head[v]}; head[v] = tot++;
    }
    Tarjan(1, 0); // 从节点1开始遍历

    // 缩点：为每个边双连通分量分配唯一编号
    int cnt = 0; // 缩点后的节点数
    for (int i = 1; i <= n; i++) {
        int root = find(i);
        if (!num[root]) num[root] = ++cnt; // 未编号的分量分配新编号
    }

    // 统计每个缩点的度数（通过遍历所有边，判断是否属于不同分量）
    memset(d, 0, sizeof(d));
    for (int i = 0; i < tot; i += 2) { // 无向图每条边处理一次
        int u = e[i].u, v = e[i].v;
        int fu = num[find(u)], fv = num[find(v)];
        if (fu != fv) { // 属于不同分量，度数加一
            d[fu]++;
            d[fv]++;
        }
    }

    // 统计叶子节点数（度数为1的缩点）
    int leaf = 0;
    for (int i = 1; i <= cnt; i++) {
        if (d[i] == 1) leaf++;
    }

    // 计算最少需要添加的边数：(leaf + 1) / 2
    printf("%d\n", (leaf + 1) / 2);

    return 0;
}

关键点解释

1. Tarjan算法：通过深度优先搜索遍历图，利用dfn和low值判断桥。非桥边的两个节点属于同一个边双连通分量，通过并查集合并。
2. 缩点：将每个边双连通分量用并查集的根节点表示，分配唯一编号，构建块树。
3. 度数统计：遍历所有边，若边连接两个不同的分量，则对应缩点的度数加一。
4. 叶子节点处理：块树中叶子节点数为leaf，每添加一条边可连接两个叶子节点，减少两个叶子节点，因此最少边数为(leaf + 1) / 2。

该算法时间复杂度为O(N + M)，适用于题目给定的数据规模。