边双连通分量模板
求出边双连通分量，缩点后成为一个树。
若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么
至少增加的边数 =（ 这棵树总度数为1的结点数 + 1 ）/ 2
1 #include<cstdio> 2 #include<iostream> 3 #include<vector> 4 using namespace std; 5 const int N=1010; 6 int n,m; 7 vector<int>g[N]; 8 int dfn[N],low[N],timer,sta[N],top,cnt,d[N],ans,color[N]; 9 bool gg[N][N]; 10 void tarjan(int k,int fa){ 11 dfn[k]=low[k]=++timer; 12 sta[top++]=k; 13 for(int i=0;i<g[k].size();i++){ 14 int x=g[k][i]; 15 if(x==fa) continue; 16 if(!dfn[x]){ 17 tarjan(x,k); 18 low[k]=min(low[k],low[x]); 19 }else if(dfn[x]<dfn[k]) low[k]=min(low[k],dfn[x]); 20 } 21 if(low[k]==dfn[k]){ 22 cnt++; 23 while(sta[top]!=k) top--,color[sta[top]]=cnt; 24 } 25 return; 26 } 27 int main(){ 28 int t1,t2; 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=m;i++){ 31 scanf("%d%d",&t1,&t2); 32 g[t1].push_back(t2);g[t2].push_back(t1); 33 } 34 tarjan(1,0); 35 for(int i=1;i<=n;i++) 36 for(int j=0;j<g[i].size();j++){ 37 int x=g[i][j]; 38 if(color[x]!=color[i]&&!gg[color[i]][color[x]]) 39 d[color[x]]++,d[color[i]]++,gg[color[i]][color[x]]=gg[color[x]][color[i]]=1; 40 } 41 for(int i=1;i<=cnt;i++) if(d[i]==1) ans++; 42 printf("%d",(ans+1)/2); 43 return 0; 44 }