題意很簡單，一個無向圖，要求在圖中添加最少的邊，使得任意兩節點間均有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