学步园

之前只是听说过双连通分量，没有自己去写过，这次遇到了果断没有做出来，看题的时候算法是想到了的，奈何实在太挫了，写不出来。之前想用dfs找环再标记缩点，结果wa了，不知道怎么调就放弃了。今天看了一下Tarjan找桥和割点的方法还是比较简单的，当dfn[u]<low[v]时，就表示v顶点不经过父子边能到达的最远的点dfs编号比u小，就说明没有其他路可以到达u，故u->v是桥，然后标记一下，重新建图，求一个直径就好了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
#define MAXM 2000005
#define MAXN 200005
struct Edge
{
    int v,next;
    bool inbridge;
}edge[MAXM];
int head[MAXN],e;
void addedge(int u,int v)
{
    edge[e].v=v;
    edge[e].next=head[u];
    edge[e].inbridge=false;
    head[u]=e++;
    edge[e].v=u;
    edge[e].next=head[v];
    edge[e].inbridge=false;
    head[v]=e++;
}
int dfn[MAXN],low[MAXN],sign,bridge;
int instack[MAXN],scnt,belong[MAXN];
stack<int> s;
vector<int> g[MAXN];
void tarjan(int u,int p)
{
    s.push(u);
    dfn[u]=low[u]=++sign;
    bool flag=true;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==p&&flag)
        {
            flag=false;
            continue;
        }
        if(!dfn[v])
        {
            tarjan(v,u);
            if(low[u]>low[v])
                low[u]=low[v];
            if(dfn[u]<low[v])
            {
                bridge++;
                edge[i].inbridge=true;
                edge[i^1].inbridge=true;
            }
        }
        else if(low[u]>dfn[v])
            low[u]=dfn[v];
    }
    if(dfn[u]==low[u])
    {
        int i;
        scnt++;
        do
        {
            i=s.top();s.pop();
            instack[i]=false;
            belong[i]=scnt;
        }
        while(i!=u);
    }
}
void work()
{
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(instack,0,sizeof(instack));
    sign=scnt=bridge=0;
    tarjan(1,0);
}
struct Node
{
    int v,dis;
    Node(int a,int b){v=a,dis=b;}
};
bool vis[MAXN];
int maxlen;
int bfs(int k)
{
    memset(vis,0,sizeof(vis));
    queue<Node> q;
    q.push(Node(k,0));
    int len=0,node=1;
    vis[k]=true;
    while(!q.empty())
    {
        Node u=q.front();
        q.pop();
        for(int i=0;i<g[u.v].size();i++)
        {
            int v=g[u.v][i];
            if(!vis[v])
            {
                vis[v]=true;
                if(len<u.dis+1)
                {
                    len=u.dis+1;
                    node=v;
                }
                q.push(Node(v,u.dis+1));
            }
        }
    }
    maxlen=len;
    return node;
}
int main()
{
    //freopen("input.txt","r",stdin);
    int n,m;
    while(scanf("%d%d",&n,&m),n+m)
    {
        memset(head,-1,sizeof(head));
        e=0;
        for(int i=1;i<=n;i++)
            g[i].clear();
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
        }
        work();
        for(int i=1;i<=n;i++)
        {
            for(int j=head[i];j!=-1;j=edge[j].next)
            {
                if(edge[j].inbridge)
                {
                    g[belong[i]].push_back(belong[edge[j].v]);
                }
            }
        }
        int u=bfs(1);
        int v=bfs(u);
        printf("%d\n",bridge-maxlen);
    }
}