题意:给你n个点和m条边的无向图，问你如果多加一条边的话，那么这个图最少的桥是什么
解题思路：无向图缩点和树的直径，用并查集缩点；
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxm=;
const int maxn=;
struct Edge
{
int next;int id;int to;
}edge[maxm];
int head[maxn],dist[maxn],f[maxn],low[maxn],dfn[maxn],visit[maxn];
int n,m,cnt,ans,step;
void init()
{
memset(dist,,sizeof(dist));
memset(visit,,sizeof(visit));
memset(head,-,sizeof(head));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
for(int i=;i<=n;i++)
f[i]=i;
step=ans=cnt=;
}
int findf(int u)
{
if(u==f[u])
return u;
else
{
f[u]=findf(f[u]);
return f[u];
}
}
void join(int u,int v)
{
int t1=findf(u);int t2=findf(v);
if(t1!=t2)
f[t2]=t1;
}
void add(int u,int v,int id)
{
edge[cnt].next=head[u];edge[cnt].to=v;edge[cnt].id=id;head[u]=cnt++;
edge[cnt].next=head[v];edge[cnt].to=u;edge[cnt].id=id;head[v]=cnt++;
}
void tarjan(int u,int fa)
{
low[u]=dfn[u]=++step;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;int id=edge[i].id;
if(fa==id)
continue;
if(!dfn[v])
{
tarjan(v,id);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])
{
ans++;
}
else
{
join(u,v);
}
}
else
{
low[u]=min(low[u],dfn[v]);
}
}
}
void bfs(int u)
{
visit[u]=;dist[u]=;
queue<int>q;
q.push(u);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(visit[v])
continue;
if(findf(x)==findf(v))
{
q.push(v);dist[v]=dist[x];visit[v]=;
}
else
{
q.push(v);dist[v]=dist[x]+;visit[v]=;
}
}
}
}
int main()
{
int x,y;
while(scanf("%d%d",&n,&m)&&n&&m)
{
init();
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y,i);
}
tarjan(,);
bfs();
int maxx=;int pos=;
for(int i=;i<=n;i++)
{
if(maxx<dist[i])
{
maxx=dist[i];pos=i;
}
}
memset(visit,,sizeof(visit));memset(dist,,sizeof(dist));
bfs(pos);
maxx=;
for(int i=;i<=n;i++)
{
if(maxx<dist[i])
maxx=dist[i];
}
printf("%d\n",ans-maxx);
}
}