题目描述：
给出一个无向的连通图，问最少加入几条边，才能使所给的图变为无桥的双连通图？
解题思路：
可以求出原图中所有的不包含桥的所有最大连通子图，然后对连通子图进行标记缩点，统计度为1的叶子节点leaf有多少个，答案就是（leaf+1）/2；
这个题目有重边，在处理的时候要注意下。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 5005; 8 struct node 9 { 10 int to, next; 11 } edge[maxn*2]; 12 13 int low[maxn], dfn[maxn], head[maxn], id[maxn], in[maxn]; 14 int stack[maxn], tot, ntime, cnt, top, In; 15 void init () 16 { 17 tot = ntime = cnt = top = In = 0; 18 memset (in, 0, sizeof(in)); 19 memset (id, 0, sizeof(id)); 20 memset (low, 0, sizeof(low)); 21 memset (dfn, 0, sizeof(dfn)); 22 memset (head, -1, sizeof(head)); 23 memset (stack, 0, sizeof(stack)); 24 } 25 void Add (int from, int to) 26 { 27 edge[tot].to = to; 28 edge[tot].next = head[from]; 29 head[from] = tot++; 30 } 31 void Tarjan (int u, int father) 32 { 33 int k = 0; 34 low[u] = dfn[u] = ++ntime; 35 stack[top++] = u; 36 for (int i=head[u]; i!=-1; i=edge[i].next) 37 { 38 int v = edge[i].to; 39 if (v==father && !k) 40 {//判定重边 41 k++; 42 continue; 43 } 44 if (!dfn[v]) 45 { 46 Tarjan (v, u); 47 low[u] = min (low[v], low[u]); 48 } 49 else 50 low[u] = min (low[u], dfn[v]); 51 } 52 if (low[u] == dfn[u]) 53 { 54 cnt ++; 55 while (1) 56 {//对同一个连通块内的点染色 57 int v = stack[--top]; 58 id[v] = cnt; 59 if (v == u) 60 break; 61 } 62 } 63 } 64 int main () 65 { 66 int n, m; 67 while (scanf ("%d %d", &n, &m) != EOF) 68 { 69 init (); 70 while (m --) 71 { 72 int u, v; 73 scanf ("%d %d", &u, &v); 74 Add (u, v); 75 Add (v, u); 76 } 77 for (int i=1; i<=n; i++) 78 if (!dfn[i]) 79 Tarjan (i, 0); 80 for (int i=1; i<=n; i++) 81 for (int j=head[i]; j!=-1; j=edge[j].next) 82 { 83 int u = id[i]; 84 int v = id[edge[j].to]; 85 if (v != u) 86 {//统计缩点后的图中每个点的度 87 in[v] ++; 88 in[u] ++; 89 } 90 } 91 for (int i=1; i<=cnt; i++) 92 if (in[i] == 2)//因为是无向图建图方式的原因，当度为2的时候才是叶子节点 93 In ++; 94 printf ("%d ", (In+1)/2); 95 } 96 return 0; 97 }