思路：
每次枚举删除一个点，然后对剩下的点求出关键点，判断删除哪个关键点获得的连通分支数最大。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> #define Maxn 5100 #define Maxm 50100 #define inf 0x7fffffff using namespace std; map<int,int> p[Maxn]; int Index[Maxn],dfn[Maxn],low[Maxn],vi[Maxn],compent[Maxn],e,n,lab,Max=0; struct Edge{ int from,to,next; }edge[Maxm]; inline int min(int a,int b) { return a<b?a:b; } inline int max(int a,int b) { return a>b?a:b; } void init() { memset(Index,-1,sizeof(Index)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(vi,0,sizeof(vi)); memset(compent,0,sizeof(compent)); for(int i=0;i<=n;i++) p[i].clear(); e=lab=Max=0; } void Init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(vi,0,sizeof(vi)); memset(compent,0,sizeof(compent)); lab=Max=0; } void addedge(int from,int to) { edge[e].from=from; edge[e].to=to; edge[e].next=Index[from]; Index[from]=e++; } void dfs(int u,int farther) { dfn[u]=low[u]=++lab; int i,temp; for(i=Index[u];i!=-1;i=edge[i].next) { temp=edge[i].to; if(!vi[temp]) { if(!dfn[temp]) { dfs(temp,u); if(low[temp]>=dfn[u]) { compent[u]++; //cout<<u<<" * "<<compent[u]<<" "<<low[temp]<<" "<<temp<<endl; Max=max(Max,compent[u]); } low[u]=min(low[u],low[temp]); } if(temp!=farther) low[u]=min(low[u],dfn[temp]); } } } int main() { int i,j,m,a,b; while(scanf("%d%d",&n,&m)!=EOF) { init(); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); a++; b++; if(!p[a][b]) { addedge(a,b); addedge(b,a); p[a][b]=p[b][a]; } } int num=0; int v; int ans=0; int flag=1; for(i=1;i<=n;i++) { Init(); vi[i]=1; num=0; flag=1; for(j=1;j<=n;j++) { if(!vi[j]&&!dfn[j]) { compent[j]=-1; dfn[j]=low[j]=++lab; num++; for(int k=Index[j];k!=-1;k=edge[k].next) { v=edge[k].to; if(!dfn[v]&&!vi[v]) { flag=0; compent[j]++; Max=max(Max,compent[j]); dfs(v,j); } } } } if(flag) num--; vi[i]=0; ans=max(ans,num+Max); //cout<<num<<" "<<Max<<endl; } printf("%d ",ans); } return 0; }