题目链接
题意：问要添加几条边才能使所给无向图图变成边双连通图。
思路：一个有桥的连通图，如何把它通过加边变成边双连通图？方法为首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。
统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。
代码：
#include
#include
#include
#include
#include
using namespace std; const int MAXN = 5005; vector
g[MAXN]; int pre[MAXN], low[MAXN], dg[MAXN], dfs_clock; bool vis[MAXN], map[MAXN][MAXN]; int n, r; void tarjan(int u, int fa) { pre[u] = low[u] = ++dfs_clock; vis[u] = 1; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v == fa) continue; if (!pre[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if (vis[v]) { low[u] = min(low[u], pre[v]); } } } void find_ebc() { memset(pre, 0, sizeof(pre)); memset(low, 0, sizeof(low)); memset(vis, 0, sizeof(vis)); dfs_clock = 0; for (int i = 1; i <= n; i++) if (!pre[i]) tarjan(i, -1); } int main() { while (scanf("%d%d", &n, &r) != EOF) { for (int i = 1; i <= n; i++) g[i].clear(); memset(map, 0, sizeof(map)); int u, v; for (int i = 0; i < r; i++) { scanf("%d%d", &u, &v); if (!map[u][v]) { g[u].push_back(v); g[v].push_back(u); map[u][v] = map[v][u] = 1; } } find_ebc(); memset(dg, 0, sizeof(dg)); for (int u = 1; u <= n; u++) { for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (low[u] != low[v]) dg[low[u]]++; } } int cnt = 0; for (int i = 1; i <= n; i++) if (dg[i] == 1) cnt++; printf("%d\n", (cnt + 1) / 2); } return 0; }