题意：求一个无向图的，去掉两个不同的点后最多有几个连通分量。
思路：枚举每个点，假设去掉该点，然后对图求割点后连通分量数，更新最大的即可。算法相对简单，但是注意几个细节：
1：原图可能不连通。
2：有的连通分量只有一个点，当舍去该点时候，连通分量-1；
复习求割点的好题！
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
vector<vector<int> >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<e[u].size();i++){int v=e[u][i];if(v==rf)continue; // 这里注意，舍去的点不要了if(!vis[v]){vis[v]=1;tarjan(v,u);if(low[v]<low[u])low[u]=low[v];if(u==root) //求割点是根的情况{son++;}else // 其他情况{if(dfn[u]<=low[v]) //subset【u】+1记录 以u为割点后形成的连通分量数subset[u]++;}}else if(v!=fa) //条件注意{if(dfn[v]<low[u])low[u]=dfn[v];}}return ;
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=0;i<=n;i++){dfn[i]=low[i]=subset[i]=vis[i]=0;e[i].clear();}int ta,tb;for(int i=0;i<m;i++){scanf("%d%d",&ta,&tb);e[ta].push_back(tb);e[tb].push_back(ta);}int maxx=0;for(int i=0;i<n;i++) //枚举每个点{rf=i; //i舍去vis[rf]=1;int scc=0;int maxson=0;for(int iii=0;iii<n;iii++) //考虑原图不连通！{if(!vis[iii]){vis[iii]=1;root=iii;tarjan(iii,-1);scc++; //连通分量数if(son>maxson)maxson=son; //求出每个连通分量的根的最大的sonson=0; //每个连通分量要更新son}}if(e[i].size()==0)scc--; // 注意点！！！：该连通分量只有一个点！舍去的话就没了。for(int ii=0;ii<n;ii++) //取最大的{if(scc+subset[ii]+1-1>maxx)maxx=scc+subset[ii]+1-1;}if(scc+maxson-1>maxx)maxx=maxson+scc-1; for(int j=0;j<n;j++) //不忘更新！{dfn[j]=low[j]=subset[j]=vis[j]=0;}son=times=0;}cout<<maxx<<endl;}return 0;
}
