题意抽象后为：
给定一个无向图
问添加一条边的情况下最少能有多少个桥。
桥的定义：删除该边后原图变为多个连通块。
数据规模:点数N(2<=N<=200000),边数M(1<=M<=1000000)
缩点之后求一下树的直径就好了，最优加边方案显然为连接直径的头尾。
AC代码：
#include<cstdio> #include<cstring> #include<queue> #define rep(i,a,b) for(int i=a;i<=b;++i) using namespace std; const int MAXV=210000; const int MAXE=2210000; int DFN[MAXV],low[MAXV],par[MAXV],label[MAXV]; int pointer[MAXV]; int tot,cnt,m,n,Bcnt,ans; vector<int> graph[MAXV]; int dep[MAXV]; struct Edge { int to,next; bool vis; Edge() {} Edge(int b,int nxt,int flag) {to=b,next=nxt,vis=flag;} }edge[MAXE]; inline void addedge(int a,int b) { edge[tot]=Edge(b,pointer[a],0); pointer[a]=tot++; edge[tot]=Edge(a,pointer[b],0); pointer[b]=tot++; } void init() { tot=0; cnt=0;Bcnt=0; memset(pointer,-1,sizeof(pointer)); memset(label,0,sizeof(label)); memset(DFN,0,sizeof(DFN)); rep(i,1,n) { graph[i].clear(); } } void tarjan(int u) { DFN[u]=low[u]=++cnt; for(int j=pointer[u];j!=-1;j=edge[j].next) { int v=edge[j].to; if(edge[j].vis) continue; edge[j].vis=edge[j^1].vis=1; if(!DFN[v]) { par[v]=j; tarjan(v); if(low[v]<low[u]) low[u]=low[v]; } else if(low[u]>DFN[v]) low[u]=DFN[v]; } } void part(int u) { label[u]=Bcnt; for(int j=pointer[u];j!=-1;j=edge[j].next) { int v=edge[j].to; if(!label[v]&&edge[j].vis) part(v); } } void bfs(int s) { rep(i,1,Bcnt) dep[i]=-1; queue<int > q; dep[s]=0; q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int j=0;j<graph[u].size();++j) { int v=graph[u][j]; if(dep[v]==-1) { dep[v]=dep[u]+1; q.push(v); } } } } int diameter() { bfs(1); int ma=0,tag; rep(i,1,Bcnt) { if(dep[i]>ma) { tag=i; ma=dep[i]; } } bfs(tag); ma=0; rep(i,1,Bcnt) { if(dep[i]>ma) { tag=i; ma=dep[i]; } } return ma; } int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)==2&&(n+m)) { init(); int u,v; rep(i,1,m) { scanf("%d%d",&u,&v); addedge(u,v); } tarjan(1); int tmp; rep(i,2,n) { tmp=par[i]^1; u=edge[tmp].to; if(low[i]>DFN[u]) { edge[tmp].vis=0; edge[tmp^1].vis=0; } } Bcnt=0; rep(i,1,n) { if(!label[i]) { Bcnt++; part(i); } } rep(i,2,n) { if(!edge[par[i]].vis) { tmp=par[i]^1; u=edge[tmp].to; graph[label[u]].push_back(label[i]); graph[label[i]].push_back(label[u]); } } printf("%d ",Bcnt-1-diameter()); } return 0; }