题目大意：给出一张无向图。问加入多少边才干使得这张无向图变成边双连通分量
解题思路：先求出全部的边双连通分量。再将边双连通缩成一个点。通过桥连接起来。这样就形成了一棵无根树了
如今的问题是，将这颗无根树变成边双连通分量网上的解释是：统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上加入(leaf+1)/2条边，就能使树达到边二连通，所以至少加入的边数就是(leaf+1)/2。具体方法为。首先把两个近期公共祖先最远的两个叶节点之间连接一条边，这样能够把这两个点到祖先的路径上全部点收缩到一起，由于一个形成的环一定是双连通的。
然后再找两个近期公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把全部点收缩到了一起。
附上大神的
和相关的连通分量的#include#include #define N 1010#define min(a,b) ((a)<(b) ?(a):(b))struct Edge{ int to, next;}E[N*2];int n, m, tot, dfs_clock, bcc_cnt, top, bnum;;int head[N], pre[N], belong[N], degree[N], stack[N], bridge[N][2];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, -1, sizeof(head)); tot = 0; int u, v; for (int i = 0; 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 != -1; 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][0] = u; bridge[bnum++][1] = v; bcc_cnt++; while (1) { 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, 0, sizeof(degree)); memset(pre, 0, sizeof(pre)); dfs_clock = bcc_cnt = top = bnum = 0; dfs(1, -1); if (top) { bcc_cnt++; while (1) { int x = stack[top--]; belong[x] = bcc_cnt; if (x == 1) break; } } for (int i = 0; i < bnum; i++) { int u = bridge[i][0]; int v = bridge[i][1]; degree[belong[u]]++; degree[belong[v]]++; } int leaf = 0; for (int i = 1; i <= bcc_cnt; i++) if (degree[i] == 1) leaf++; printf("%d\n", (leaf + 1)/ 2);}int main() { while (scanf("%d%d", &n, &m) != EOF) { init(); solve(); } return 0;}