题意：给出一个连通图，求最少加入多少条边可使图变成一个 边-双连通分量
模板题，熟悉一下边连通分量的定义。最后ans=(leaf+1)/2。leaf为原图中size为1的边-双连通分量
#include<cstdio> #include<vector> #include<algorithm> #include<stack> #include<cstring> using namespace std; const int maxn=5005; int n,m; vector<int> adj[maxn]; int dfn[maxn],low[maxn]; int time_tag; int ebccno[maxn],ebcc_cnt; int size[maxn]; //size[i]用来记录编号为i的ebcc的size stack<int> st; void init() { memset(dfn,0,sizeof(dfn)); memset(size,0,sizeof(size)); memset(ebccno,0,sizeof(ebccno)); time_tag=ebcc_cnt=0; for(int i=0;i<=n;i++) adj[i].clear(); } void dfs(int u,int pre) { dfn[u]=low[u]=++time_tag; st.push(u); // for(int v:adj[u]) for(int i=0;i<adj[u].size();i++) { int v=adj[u][i]; if(v==pre) continue; if(!dfn[v]) { dfs(v,u); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ++ebcc_cnt; while(1) { int x=st.top();st.pop(); ebccno[x]=ebcc_cnt; if(x==u) break; } } } void find_ebcc() { for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,-1); } int solve() { int ret=0; for(int u=1;u<=n;u++) // for(int v:adj[u]) for(int i=0;i<adj[u].size();i++) { int v=adj[u][i]; if(ebccno[u]!=ebccno[v]) //边(u,v)为bridge size[ebccno[u]]++,size[ebccno[v]]++; } for(int i=1;i<=ebcc_cnt;i++) if(size[i]==2) ret++; return ret; } int main() { while(~scanf("%d%d",&n,&m)) { init(); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } find_ebcc(); int leaf=solve(); printf("%d ",(leaf+1)/2); } }