求出每个边双连通分量缩点后的度，度为1的点即叶子节点。原图加上（leaf+1）/2条边即可变成双连通图。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <map> using namespace std; const int N = 5010; const int M = 10010; struct Edge { int to,next; bool cut; }edge[M]; int head[N],tot; int Low[N],DFN[N],Stack[N],Belong[N]; int Index,top; int block; bool Instack[N]; int bridge; void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; edge[tot].cut=false; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];~i;i = edge[i].next) { v = edge[i].to; if(v == pre)continue; if( !DFN[v] ) { Tarjan(v,u); if( Low[u] > Low[v] )Low[u] = Low[v]; if(Low[v] > DFN[u])//桥 { bridge++; edge[i].cut = true; edge[i^1].cut = true; } } else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { block++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = block; } while( v != u); } } int du[N];//缩点后形成树，每个点的度数 void solve(int n) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof Instack); Index = block = top = 0; Tarjan(1,0); int ans = 0; memset(du,0,sizeof(du)); for(int i = 1;i <= n;i++) for(int j = head[i];~j;j = edge[j].next) if(edge[j].cut) du[Belong[i]]++; for(int i = 1;i <= block;i++) if(du[i]==1) ans++; printf("%d ",(ans+1)/2); } void init() { tot = 0; memset(head,-1,sizeof head); } int main() { int n,m; int u,v; while(scanf("%d%d",&n,&m)==2) { init(); while(m--) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } solve(n); } return 0; }