总的来说，就是求最少加几条边，使图成为一个边双连通图。
显然先边双连通分量缩点，于是图就变成了一棵树（因为是无向图），然后我就在纸上画了半天，得到了一个结论：只要连叶子节点数 / 2（向上取整）条边，这颗树就成了一个边双连通图。
就是叶子之间两两连边，然后如果是奇数个叶子节点，就把多的那个向根节点连一条边。而且奇特的是，并不是所有连边方案都可行，但却一定有至少一种方案可以。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e3 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, m; 38 vector<int> v[maxn]; 39 40 stack<int> st; 41 bool in[maxn]; 42 int dfn[maxn], low[maxn], cnt = 0; 43 int col[maxn], ccol = 0; 44 void tarjan(int now, int fa) 45 { 46 dfn[now] = low[now] = ++cnt; 47 st.push(now); in[now] = 1; 48 for(int i = 0; i < (int)v[now].size(); ++i) 49 { 50 if(!dfn[v[now][i]]) 51 { 52 tarjan(v[now][i], now); 53 low[now] = min(low[now], low[v[now][i]]); 54 } 55 else if(v[now][i] != fa) low[now] = min(low[now], dfn[v[now][i]]); 56 //第一次知道这还得有个判断 57 } 58 if(dfn[now] == low[now]) 59 { 60 int x; ++ccol; 61 do 62 { 63 x = st.top(); st.pop(); 64 in[x] = 0; 65 col[x] = ccol; 66 }while(x != now); 67 } 68 } 69 70 int Cnt = 0; 71 vector<int> v2[maxn]; 72 int to[maxn]; 73 void newGraph(int now) 74 { 75 int u = col[now]; 76 for(int i = 0; i < (int)v[now].size(); ++i) 77 { 78 int e = col[v[now][i]]; 79 if(u == e) continue; 80 v2[u].push_back(e); v2[e].push_back(u); 81 } 82 } 83 84 int solve(int now) //判断度为 1 的点，就是叶子节点 85 { 86 int pos = 0, flg = -1; //flg : -1代表无出边，0为一条，大于1为一条以上 87 for(int i = 0; i < (int)v2[now].size(); ++i) 88 { 89 if(flg == -1) pos = v2[now][i], flg = 0; 90 if(pos != v2[now][i]) flg++; 91 } 92 return flg == 0; 93 } 94 95 int main() 96 { 97 n = read(); m = read(); 98 for(int i = 1; i <= m; ++i) 99 { 100 int x = read(), y = read(); 101 v[x].push_back(y); v[y].push_back(x); 102 } 103 for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i, 0); 104 for(int i = 1; i <= n; ++i) newGraph(i); 105 for(int i = 1; i <= ccol; ++i) Cnt += solve(i); 106 write((Cnt + 1) >> 1); enter; 107 return 0; 108 }