做了非常久......
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=4587
先枚举删除的第一个点，第二个点就是找割点。没有割点当然也有答案
学到的：
1、图论硬套模板不太现实，比方这道题，我能想到孤立点是特殊情况，删除孤立点。连通分支个数会降低一，可是一直处理不好，最后按缩点的做法搞了。
推断是不是孤立点的方法：
就是先用一个数组scnt[i]=j，vv[j]++ 表示点i在以j为祖先的联通分支里，并且每次都让vv[j]++，就使得vv[j]表示以j为祖先的连通分支的点的个数为vv[j]，这个但是没模版的。自己乱改搞出来的，開始试了几种其它方法都WA。。。
2、我自己的求割点的模板里，subset[i]==0的时候，就表示删除该点的时候。其连通分支数没有添加，这包括了悬挂顶点和孤立顶点。求是不是割点的时候。仅仅要subset[v]>0，那么v就是割点，可是在求删除该点之后的连通分支个数的时候，悬挂顶点和孤立顶点这两种情况是要分开的，假设subset[i]==0
&& i是悬挂顶点。连通分支数目不变。假设subset[i]==0 && i是孤立点。连通分支数目减一。所以1中推断是不是孤立点的方法还是比較重要的
3、这道题開始的时候全然没有思路。由于一直想的都是“两个点一起删除怎么让连通分支数目最多“，而没有尝试这么思考：”想删一个点，然后在删除一个点“（就是说放一块思考想不出来就一步一步想），也没有这么思考”不知道怎么做决策的时候就枚举“，由于时间12s。足够枚举。我的代码也在6000ms之内跑出来了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std; const int MAXN =5000*2+100;
struct Node
{
int to,next,from;
int u;
}e[MAXN];
int n,m;
int head[MAXN];
int vis[MAXN],son, subset[MAXN],dfn[MAXN],low[MAXN],tmpdfn,first,vv[MAXN],scnt[MAXN];
void init()
{
memset(head,-1,sizeof(head));
for(int i=0;i<n*2+10;i++)e[i].from=-1;
} void addedge(int u,int v,int k)
{
e[k].to=v;
e[k].from=u;
e[k].next=head[u];
//e[k].u=0;
head[u]=k;
}
int rt;
void init2()
{
tmpdfn=0;
memset(subset,0,sizeof(subset));
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(vv,0,sizeof(vv));
memset(scnt,-1,sizeof(scnt));
} void dfs(int u)
{
dfn[u]=low[u]=++tmpdfn;
for(int j=head[u];j!=-1;j=e[j].next)
{
if(e[j].to!=first)//
{
int v=e[j].to;
if(!vis[v])
{
vis[v]=1;
scnt[v]=rt,vv[rt]++;
dfs(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
if(u == rt)son++;
else subset[u]++;
}
}
else
{
low[u]=min(low[u],dfn[v]);
}
}
}
} int solve()
{
int ans=0,cnt=0;
for(int k=0;k<n;k++)
{
//删点
first=k;
init2();
cnt=0; for(int i=0;i<n;i++)
{
if(i!=first)
{
if(!vis[i])
{
son=0;
rt=i;
cnt++;
vis[i]=1;
scnt[rt]=rt,vv[rt]++;
dfs(i);
if(son)subset[rt]=son-1;
}
}
}
int pos=-1,mmax=0;
for(int i=0;i<n;i++)
if(i != first )//ans=max(ans,subset[i]+cnt);//cnt-1+subset[i]+1
{
if(mmax<subset[i]+cnt)
{
pos=i;
mmax=subset[i]+cnt;
}
}
if(vv[scnt[pos]] == 1)mmax--;//不是割点。去掉该点后，连通分支数不会添加
ans=max(ans,mmax);
}
return ans;
} int main()
{
//freopen("hdu4587.txt","r",stdin);
int u,v,k;
while(~scanf("%d%d",&n,&m))
{
init();
for(int i=0,k=0;i<m;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v,k++);
addedge(v,u,k++);
}
printf("%d\n",solve());
}
return 0;
}