题意如上，含有重边（重边的话，俩个点就可以构成了边双连通）。

先缩点成树，在求数的直径，最远的连起来，剩下边（桥）的自然最少。这里学习了树的直径求法：第一次选任意起点U，进行bfs，到达最远的一个点v（level最深）该点必然是树的直径的一个端点，,再从该点出发，bfs，到最深的一点，该点深度就是直径。（证明：先假设u，是直径上一点，S,T是直径的端点，设v!=t,则有（V,U)+(U,S)>(T,U)+(U,S),矛盾，故t=v；若u不是直径上一点，设u到直径上的一点为x，同理易证。

最后 缩点后树的边-直径即可。

再说说这次，哎，先是爆栈，没有在C++申请空间。。。 无向图的tarjian太不熟练了！很久没敲了。。。。

注意点：无向图求边双连通，缩点，可以这样：

法1：必需用前向星来保存边，然后标记访问边（同时标记反向边）的方法来处理。这样，重边的话，就在字自然在一个边通分量中了。（要求边数可以用数组存下），这样不用！=-father来判断。

法2，重边视为单边（只有俩个点不连通），不标记边，多一个参数father，在返祖边更新我的时候，加判断！=father。

#pragma comment(linker, "/STACK:10240000000000,10240000000000")        //申请空间
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          using namespace std; const int maxv=300010; int dfn[maxv];int low[maxv];int visited[maxv]; int ins[maxv];stack
         
          sta;int scc[maxv]; int times=0;int block=0; int n,m; int minn(int a,int b) { if(a<=b)return a; return b; } int nume=0;int e[2000500][2];int head[maxv]; void inline adde(int i,int j) //原图 { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume++; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume++; } int nume2=0;int newg[2000500][2];int head2[maxv]; void inline adde2(int i,int j) //新图 { newg[nume2][0]=j;newg[nume2][1]=head2[i];head2[i]=nume2++; newg[nume2][0]=i;newg[nume2][1]=head2[j];head2[j]=nume2++; } bool marke[2001000]; //标记边的访问 void tarjan(int u) { dfn[u]=low[u]=++times; ins[u]=1; sta.push(u); for(int i=head[u];i!=-1;i=e[i][1]) { int child=e[i][0]; if(marke[i])continue; //注意放在这里，否则下面的会更新，起不了作用 if(visited[child]==0) { visited[child]=1; marke[i]=marke[i^1]=1; //标记双向 tarjan(child); low[u]=minn(low[u],low[child]); } else if(ins[child]) { low[u]=minn(dfn[child],low[u]); } } if(low[u]==dfn[u]) //同一个边双连通 { block++; int cur; do { cur=sta.top(); ins[cur]=0; sta.pop(); scc[cur]=block; }while(cur!=u); } } void rebuild() { for(int i=1;i<=n;i++) //遍历所有边，来重新建图，若在同一个边双连通中，则有边。 { for(int j=head[i];j!=-1;j=e[j][1]) { int ch=e[j][0]; if(scc[i]!=scc[ch]) adde2(scc[i],scc[ch]); } } } int lev[maxv]; void bfsgetlev(int ss) //BFS分层 { memset(lev,0,sizeof(lev)); memset(visited,0,sizeof(visited)); queue
          
           q; q.push(ss); visited[ss]=1; while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=head2[cur];i!=-1;i=newg[i][1]) { int vv=newg[i][0]; if(!visited[vv]) { lev[vv]=lev[cur]+1; q.push(vv); visited[vv]=1; } } } return ; } void init() { block=times=0;nume=0;nume2=0; memset(marke,0,sizeof(marke)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(visited,0,sizeof(visited)); memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); } int main() { while(scanf("%d%d",&n,&m)!=EOF&&(n||m)) { init(); int a,b; for(int i=0;i
           
            maxx) { maxx=lev[i]; froms=i; } } bfsgetlev(froms); //最远点（直直径的一个端点） for(int i=1;i<=block;i++) { if(lev[i]>maxx) { maxx=lev[i]; } } ans=block-1-maxx; printf("%d\n",ans); } return 0; }