tarjan原理看这里

/*
3 割点
    割点 
 o-o   o-o
 |  \↓/  |
 o-o-o-o-o 
3.1求割点
     x   
     |
     y
要求low[y] > dfn[x] y能到达的最早的节点>x的时间戳
否则low[y] ≤ dfn[x]时,即y能到比xdfs序小的点,则存在环
    →o
   | ↓    
   | x   
   | |
   o←y
low[y]≤dfn[x]的情况下
1 如果x不是根节点 那么x是割点
2 x是根节点 至少有两个子节点yi 
            且有low[yi]≥dfn[x]
            如果只有一个子结点 去完根节点x
            x   
            |   →   y1  子节点部分还是连通的
            y1
            如果有两个子结点 去完根节点x
            x  
           / \  →   y1  y2 之间不连通
          y1 y2 
3.2 求点双连通分量
     o x
     |
     o y
stk[]
if(dfn(x)<=low(y))
{
    cnt++
    if(x非根||cnt>1)x是割点
    stk.pop(j) while j!=y将栈中元素弹出至y为止
    且x也属于该 点双连通分量
}
样例1
 0 - 1      0 - 1
  \ /     →        1个(不管删除哪个点都是连通的)
   2          
样例2
 0 - 1      0       
 2 - 3      2 - 3  2个(删除1后仍有0 和2-3两个连通块)
样例3
 0 - 1  删1还剩两个块 0 and 2
 2      删2还剩一个块 0-1
1 统计连通块个数cnt
2 枚举从哪个块j中删
  2.1 从块j中删除哪个点i
  2.2 删除点i后块j分成s部分(在样例3中删2后s=0)
      总共分成的部分 = s(i新的子块的个数)+cnt(删前总的连通块数)-1(删前子块的个数)
                     = 当前块的部分(s)+剩余连通块的数量(cnt-1)
                     = 1+1-1 (样例1:删2后 s=1 cnt=1 -1 =1
                     = 1+2-1 (样例2:删1后 s=1 cnt=2 -1 =2
                     = max(1+2-1,0+2-1)(样例3:删1后 s=1 cnt=2 -1=2 
                                              删2后 s=0 cnt=2 -1=1(点2所在的块删除2后没有点了 s=0)
                    dfn(x)<=low(y)
                    x删掉后y单独出来--多一个单独子树
                    如果x非根节点 还要多+1
                     /
                    x       
                   / \
    问题转化为依次删除每个割点
    求全局最大值

*/  
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 30010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int root, ans;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    int cnt = 0;//当前块内 已经可以分出来的子树的个数
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])//没有遍历过j
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);//用j更新u
            if (low[j] >= dfn[u]) cnt ++ ;//j为割点 则多一个连通块
        }
        else low[u] = min(low[u], dfn[j]);
    }
    if (u != root) cnt ++ ;
    //如果不是根节点
    /*
             /
            x    删掉x后 除子节点yi外
           / \           还要要加上父节点部分+1
          o   o

    */
    ans = max(ans, cnt);
}
int main()
{
    while (cin >> n >> m, n || m)
    {
        memset(dfn, 0, sizeof dfn);
        memset(h, -1, sizeof h);
        idx = timestamp = 0;

        while (m -- )
        {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }

        ans = 0;//把每个点删完后 最多能分为几块
        int cnt = 0;//连通块数量
        for (root = 0; root < n; root ++ )
            if (!dfn[root])//如果点root没搜索过 连通块数+1
            {
                cnt ++ ;
                tarjan(root);
            }

        cout << ans + cnt - 1 << endl;
    }

    return 0;
}