题目链接：传送门
思路：
题目要将使每一对草场之间都有至少两条相互分离的路径，所以转化为（一个有桥的连通图至少加几条边才能变为双联通图？）
先将桥删除，然后原图变为多个连通块，每一个连通块就是一个边双联通分量，将双联通子图收缩为一个顶点，再把桥边加回来，边连通度为1，
顺便统计度为1的节点的个数，即叶节点的个数即为cnt，所以至少在树上添加（cnt+1）/2条边。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxn = 10010; struct Edge{ int u,v; }; Edge tmp; vector <Edge> ee; int num[maxn],vis[maxn],low[maxn],fa[maxn],tog[maxn],m,n,tim; vector <int> vc[maxn]; void Init() { memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); memset(fa,0,sizeof(fa)); memset(tog,0,sizeof(tog)); ee.clear(); for(int i=0;i<maxn;i++) vc[i].clear(); tim=1; } int MIN(int x,int y) { return x<y?x:y; } int f(int x) { if(fa[x]==0) return x; else return fa[x]=f(fa[x]); } void Tarjan(int v,int pre) { int i,w; vis[v]=1; low[v]=num[v]=tim++; for(i=0;i<vc[v].size();i++){ w=vc[v][i]; if(!vis[w]){ Tarjan(w,v); low[v]=MIN(low[v],low[w]); if(low[w]>num[v]){ tmp.u=v;tmp.v=w; ee.push_back(tmp); } else{ int t1=f(v); int t2=f(w); if(t1!=t2) fa[t2]=t1; } } else if(pre!=w) low[v]=MIN(low[v],num[w]); } } int main(void) { int i,j,x,y; while(~scanf("%d%d",&n,&m)){ Init(); for(i=0;i<m;i++){ scanf("%d%d",&x,&y); vc[x].push_back(y); vc[y].push_back(x); } Tarjan(1,-1); for(i=0;i<ee.size();i++){ int t1=f(ee[i].u); int t2=f(ee[i].v); tog[t1]++;tog[t2]++; } int cnt=0; for(i=1;i<=n;i++) if(tog[i]==1) cnt++; cnt=(cnt+1)/2; printf("%d\n",cnt); } return 0; }