hdu 4587 2013南京邀请赛B题/ / 求割点后连通分量数变形。

题意：求一个无向图的，去掉两个不同的点后最多有几个连通分量。

思路：枚举每个点，假设去掉该点，然后对图求割点后连通分量数，更新最大的即可。算法相对简单，但是注意几个细节：

1：原图可能不连通。

2：有的连通分量只有一个点，当舍去该点时候，连通分量-1；

复习求割点的好题！

#include
  
   
#include
   
     #include
    
      using namespace std; int n,m; vector
     
       >e(10010); int dfn[5010];int low[5010];int vis[5010]; int times=0; int subset[5010]; int root=0; int rf=0; int son=0; void tarjan(int u,int fa) //无向图tarjan记录父亲 { if(u==rf)return; //是被枚举的点，舍去（从图中删去）。 dfn[u]=low[u]=times++; for(int i=0;i
      
       maxson)maxson=son; //求出每个连通分量的根的最大的son son=0; //每个连通分量要更新son } } if(e[i].size()==0)scc--; // 注意点！！！：该连通分量只有一个点！舍去的话就没了。 for(int ii=0;ii
       
        maxx)maxx=scc+subset[ii]+1-1; } if(scc+maxson-1>maxx)maxx=maxson+scc-1; for(int j=0;j