学步园

题意：求去除一点后，形成的连通分支数的最大值。（使最多的网络不能跟原路线相连）

顶点u是割项当且仅满足 （1） 或 （2）时：

（1） 若u是树根，且u的孩子数 son>1 。因为没有u的后向边，以这些孩子为根的子树之间互不相连通，所以去掉u后将得到son个分支。

（2）若u不是树根，且存在树边 ( u  ,  v ) 使low ( v ) >= dfn ( u )。low值说明以v为根的子树不能到达u的祖先也就是去掉u后不能跟原图连通。（跟割绳子一样，一条绳子割n刀会形成 (n +1) 小段）所以得到 { 这样的v的个数 + 1 }个分支。

另外需要注意：

1.  若整个图没有边 ，则去掉一个点后，连通分支量为所有顶点数 -1 。

2.  因为是无向图，所以每个有边相连的子图都是一个连通分支。比如：

     n = 4   m = 2   ：  （0  ， 1）  （2   ， 3） 就是两个连通分支。

     n = 3   m = 3   ：  （ 0 ， 1）  （1  ， 2 ） （2 ， 0）    整个图就是一个联通分支。

所以  ：   ans =( 没有去除顶点u时的联通分支 - 1 )  + 去除顶点后新增的分支数 。

代码：

#include<iostream>
#include<string.h>
#include<vector>
#define mm 10010
using namespace std;

vector <int> vec[mm];
int  low[mm] , dfn[mm]  ;
int step  , son ,   ans , ma;
int n, m  ;

void init()
{
    for(int i=0;i<mm;i++)
    {
        low[i]=dfn[i]= 0;
        vec[i].clear();
    }
    step=son= ans=ma=0;
}
void insert(int u , int v)
{
    vec[u].push_back(v);
    vec[v].push_back(u);
}
void tarjan(int u , int rt)
{ 
    int v;
    low[u]=dfn[u]=++step;
    int child=0;  //之前将该变量定为了全局，导致错误（每次递归都会改变）
                  //而局部变量中，只有在同一个递归层才能改变child的值。 
    for(int i=0;i<vec[u].size(); i++)
    {
        v=vec[u][i];//cout<<"u= "<<u<<endl;
        if(!dfn[v])
        {
            tarjan(v , rt);
            low[u]=min(low[u] , low[v]);
            if(u==rt) son++;  
            else if(low[v]>=dfn[u])  
            {//cout<<u<<"--------"<<v<<endl;  
              child++; 
            }
        }
        else low[u]=min(dfn[v] , low[u]);
    }     cout<<"u= "<<u<<"  rt= "<<rt<<endl;
       cout<<"son= "<<son<<"   child+1= "<<child+1<<endl; 
    ans=max(child+1 , ans);     
}

int main()
{
    int a , b ,num;
    while(scanf("%d%d",&n,&m)!=EOF && n+m)
    {
        init();
        num=0;
        for(int i=0;i<m;i++) 
        {
           scanf("%d%d",&a, &b);
           insert(a , b); 
        }
        for(int i=0;i<n;i++)
        { 
            if(!dfn[i])
            {num++;
               son =0;  
            //   memset(dfn,0,sizeof(dfn));
               tarjan(i , i);
               if(son>1)  ans=max(ans , son);
               ma=max(ma, ans);
            }//cout<<"ma= "<<ma<<"   num= "<<num<<"  sum= "<<sum<<endl;
        }
        if(m==0) ma=0;
        printf("%d\n", num+ma-1);
    } 
    return 0;
}