大四真闲，也不突击比赛了，可以拿出大把的时间慢慢看点儿算法，研究一下证明，tarjan大神的三个图论算法总算是都了解了。

割点是无向图中去掉后能把图割开的点。dfs时用dfn（u）记录u的访问时间，用low（u）数组记录u和u的子孙能追溯到的最早的节点（dfn值最小）。由于无向图的dfs只有回边和树边，且以第一次dfs时的方向作为边的方向，故有：
low=min{
dfn（u），
dfn（v），若（u，v）为回边（非树边的逆边）
low（v），若（u，v）为树边
}

顶点u是割点当且仅当其满足（1）或者（2）：
（1） 若u是树根，且u的孩子数sons>1。因为没有u后，以这些孩子为根的子树间互相就不连通了，所以去掉u后得到sons个分支。
（2） 若u不是树根，且存在树边（u，v）使 low（v）>=dfn（u）。low值说明以v为根的子树不能到达u的祖先也就是去掉u后不能和原图联通，所以得到{这样的v的个数+1}个分支。

这个题是求无向图（不一定联通）中，去掉一个顶点可以形成的最多的分支数，对所有分支tarjan一下就知道了去掉哪个多了，注意孤立点的情况。求low时其实不用判断树边的逆边的情况，仔细琢磨一下，对结果没有影响，又能省很多代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 10001
typedef vector<int>::iterator it;
vector<int> g[maxn];
int dfn[maxn],low[maxn];
bool vit[maxn];
int n,idx,sons;
int ans;

void dfs(int u,bool root)
{
    vit[u]=1;
    dfn[u]=low[u]=++idx;
    int child=0;
    for(it i=g[u].begin();i!=g[u].end();++i)
    {
        int v=*i;
        if(!dfn[v])
        {
            dfs(v,false);
            low[u]=min(low[u],low[v]);
            if(root)
                sons++;
            else if(low[v]>=dfn[u])
                child++;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    ans=max(ans,child+1);
}

int tarjan(int root)
{
    if(g[root].size()==0) return 0;
    memset(dfn,0,sizeof(dfn));
    ans=idx=sons=0;
    dfs(root,true);
    if(sons>1) ans=max(ans,sons);
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int m,u,v;
    while(scanf("%d%d",&n,&m)!=EOF && n)
    {
        for(int i=0;i<n;i++)
            g[i].clear();
        while(m-->0)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        memset(vit,0,sizeof(vit));
        int ma=0,total=0;
        for(int i=0;i<n;i++)
            if(!vit[i])
                total++,ma=max(ma,tarjan(i));
        printf("%d\n",total+ma-1);
    }
}