题意抽象后为：
给定一个无向图
问添加一条边的情况下最少能有多少个桥。
桥的定义：删除该边后原图变为多个连通块。
数据规模:点数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=;
const int MAXE=;
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],);
pointer[a]=tot++;
edge[tot]=Edge(a,pointer[b],);
pointer[b]=tot++;
}
void init()
{
tot=;
cnt=;Bcnt=;
memset(pointer,-,sizeof(pointer));
memset(label,,sizeof(label));
memset(DFN,,sizeof(DFN));
rep(i,,n)
{
graph[i].clear();
}
}
void tarjan(int u)
{
DFN[u]=low[u]=++cnt;
for(int j=pointer[u];j!=-;j=edge[j].next)
{
int v=edge[j].to;
if(edge[j].vis) continue;
edge[j].vis=edge[j^].vis=;
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!=-;j=edge[j].next)
{
int v=edge[j].to;
if(!label[v]&&edge[j].vis) part(v);
}
}
void bfs(int s)
{
rep(i,,Bcnt) dep[i]=-;
queue<int > q;
dep[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int j=;j<graph[u].size();++j)
{
int v=graph[u][j];
if(dep[v]==-)
{
dep[v]=dep[u]+;
q.push(v);
}
}
}
}
int diameter()
{
bfs();
int ma=,tag;
rep(i,,Bcnt)
{
if(dep[i]>ma)
{
tag=i;
ma=dep[i];
}
}
bfs(tag);
ma=;
rep(i,,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)==&&(n+m))
{
init();
int u,v;
rep(i,,m)
{
scanf("%d%d",&u,&v);
addedge(u,v);
}
tarjan();
int tmp;
rep(i,,n)
{
tmp=par[i]^;
u=edge[tmp].to;
if(low[i]>DFN[u])
{
edge[tmp].vis=;
edge[tmp^].vis=;
}
}
Bcnt=;
rep(i,,n)
{
if(!label[i])
{
Bcnt++;
part(i);
}
}
rep(i,,n)
{
if(!edge[par[i]].vis)
{
tmp=par[i]^;
u=edge[tmp].to;
graph[label[u]].push_back(label[i]);
graph[label[i]].push_back(label[u]);
}
}
printf("%d\n",Bcnt--diameter());
}
return ;
}