题意很简单，一个无向图，要求在图中添加最少的边，使得任意两节点间均有2条或以上不同的路径。
这题本质上看是添边然后构成一个强联通图。
算法是这样，首先找到桥，将强联通分支缩点，这样构成一棵树。要把树变为强联通图，即将叶节点两两配对即可（如果有奇数个页节点，则将未配对节点再添加一条边即可）。
注意！无向图找桥的时候要对边加以标记，除非没有平行边，否则不要在DFS中用父节点防止走2环
1 # include <stdio.h>
2 # include <string.h>
3 # include <stdbool.h>
4 # define MAX 0xfffffff
5 # define min(a,b) ((a)<(b)?(a):(b))
6 int n,m;
7 int g[5001],v[20001],nxt[20001],c=0;
8 int cnt=0,low[5001],cid[5001],cnum=0;
9 bool map[5001][5001];
10 bool used[20001];
11 int stack[5001],top=-1;
12 void dfs(int pos)
13 {
14 int p,now=cnt++;
15 stack[++top]=pos;
16 low[pos]=now;
17 for(p=g[pos];p!=-1;p=nxt[p])
18 if(!used[p>>1])
19 {
20 used[p>>1]=1;
21 if(low[v[p]]==-1)
22 dfs(v[p]);
23 low[pos]=min(low[pos],low[v[p]]);
24 if(low[v[p]]>now)
25 {
26 do
27 {
28 cid[stack[top]]=cnum;
29 }while(stack[top--]!=v[p]);
30 cnum++;
31 }
32 }
33 }
34
35 int main()
36 {
37 // freopen("input.txt","r",stdin);
38 // freopen("output.txt","w",stdout);
39 int i,p,ans=0;
40 scanf("%d%d",&n,&m);
41 memset(g,-1,sizeof(g));
42 while(m--)
43 {
44 int s,t;
45 scanf("%d%d",&s,&t);
46 v[c]=t;
47 nxt[c]=g[s];
48 g[s]=c++;
49 v[c]=s;
50 nxt[c]=g[t];
51 g[t]=c++;
52
53 }
54 memset(low,-1,sizeof(low));
55 memset(used,0,sizeof(used));
56 dfs(1);
57 while(top>=0)
58 cid[stack[top--]]=cnum;
59 cnum++;
60 memset(map,0,sizeof(map));
61 for(i=1;i<=n;i++)
62 for(p=g[i];p!=-1;p=nxt[p])
63 {
64 if(cid[v[p]]!=cid[i])
65 map[cid[i]][cid[v[p]]]=map[cid[v[p]]][cid[i]]=1;
66 }
67 for(i=0;i<cnum;i++)
68 {
69 int cal=0;
70 for(p=0;p<cnum;p++)
71 cal+=map[p][i];
72 ans+=(cal==1?1:0);
73 }
74 printf("%d\n",(ans+1)>>1);
75 // system("pause");
76 return 0;
77 }
78