这个题跟POJ 2117没有丝毫区别

POJ 2117是：删去图中一个点，最多有几个连通块

HDOJ 4587是：删去图中两个点（点不同），最多有几个连通块


看到题中n的值5000，可以跑平方算法

所以我们先枚举一发要删去的第一个点，然后再跑割点的模板，取最大值即可


代码：

#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<cstring>
using namespace std;

const int maxn=10010;
const int maxm=100010;
struct Edge{
    int to,nxt;
    bool cut;
}edge[maxm];
int head[maxn],tot;
int Low[maxn],DFN[maxn],Stack[maxn],Belong[maxn];
int Index,top,block;
bool Instack[maxn];
bool cut[maxn];
int add_block[maxn];
int bridge;
int meiju;

void addedge(int u,int v){
    edge[tot].to=v;
    edge[tot].nxt=head[u];
    edge[tot].cut=false;
    head[u]=tot++;
}

void Tarjan(int u,int pre){
    int v;
    Low[u]=DFN[u]=++Index;
    Stack[top++]=u;
    Instack[u]=true;
    int son=0;
    int pre_cnt=0;
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        v=edge[i].to;
        if (v==meiju) continue;
        if (v==pre&&pre_cnt==0){
            pre_cnt++;
            continue;
        }
        if (!DFN[v]){
            son++;
            Tarjan(v,u);
            if (Low[u]>Low[v]) Low[u]=Low[v];
            if (Low[v]>DFN[u]){
                bridge++;
                edge[i].cut=true;
                edge[i^1].cut=true;
            }
            if (u!=pre&&Low[v]>=DFN[u]){
                cut[u]=true;
                add_block[u]++;
            }
        }
        else if (Low[u]>DFN[v])
            Low[u]=DFN[v];
    }
    if (u==pre&&son>1) cut[u]=true;
    if (u==pre) add_block[u]=son-1;
    Instack[u]=false;
    top--;
}

int solve(int N){
    memset(DFN,0,sizeof(DFN));
    memset(Instack,0,sizeof(Instack));
    memset(add_block,0,sizeof(add_block));
    memset(cut,false,sizeof(cut));
    Index=top=0;
    int cnt=0;
    for(int i=1;i<=N;i++)
    if (i!=meiju&&!DFN[i]){
        Tarjan(i,i);
        cnt++;
    }
    int ans=0;
    for(int i=1;i<=N;i++)
        if (i!=meiju)
            ans=max(ans,cnt+add_block[i]);
    return ans;
}

void init(){
    tot=0;
    memset(head,-1,sizeof(head));
}

int main(){
    int n,m,u,v;
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        while(m--){
            scanf("%d%d",&u,&v);
            u++;v++;
            addedge(u,v);
            addedge(v,u);
        }
        int ans=0;
        for(meiju=1;meiju<=n;meiju++)
            ans=max(ans,solve(n));
        printf("%d\n",ans);
    }
    return 0;
}