HDU 4587 TWO NODES(无向图割点)

HDU 4587 TWO NODES(无向图割点)

http://acm.hdu.edu.cn/showproblem.php?pid=4587

题意:给你一个无向图,问你从这个无向图中删除任意两个点之后所能获得的独立连通分量个数的最大值.

分析:

首先我们从0到n-1枚举需要删除的第一个点u,然后在这个G-u的新图中,我们剩下要删除的第二个点应该尽量为割点.(如果图中无割点,那也没办法了).

下面我们来处理G-u这个余图.我们令cut[i]表示删除i节点之后整个图的连通分量会在原来基础上增加cut[i]个.

首先对于非根节点i来说,如果i不是割点,那么cut[i]=0;如果i是割点,cut[i]=DFS树中i节点的儿子数.

其次对于根节点i来说,如果i在DFS树中儿子为0,那么cut[i]=-1.否则cut[i]=DFS树中i的儿子数-1.

最终在删除u节点后,我们只要对于pre[i]=0的每个节点(除了u)求一次tarjan(),就可以得出删除u的连通分量数目sum和每个cut[i].然后我们在通过求max(sum+cut[i]) 得出最优解.(这个比较抽象,还是看代码吧)

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=5000+5;
int n,m;
vector<int> G[maxn];
int dfs_clock;
int pre[maxn],low[maxn],cut[maxn];
int tarjan(int u,int fa,int forbid)//forbid节点不允许访问
{
    int lowu=pre[u]=++dfs_clock;
    int child=0;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa||v==forbid) continue;
        if(!pre[v])
        {
            child++;
            int lowv=tarjan(v,u,forbid);
            lowu=min(lowu,lowv);
            if(lowv >= pre[u])
                cut[u]++;
        }
        else lowu=min(lowu,pre[v]);
    }
    if(fa<0) cut[u]--;
    return low[u]=lowu;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=0;i<n;i++) G[i].clear();
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int ans=-100;
        for(int u=0;u<n;u++)
        {
            int sum=0;//删除u点后的连通分量数目
            dfs_clock=0;
            memset(pre,0,sizeof(pre));
            memset(cut,0,sizeof(cut));
            for(int v=0;v<n;v++)if(v!=u && !pre[v])
            {
                sum++;
                tarjan(v,-1,u);
            }
            for(int v=0;v<n;v++)if(v!=u)
                ans = max(ans,sum+cut[v]);
        }
        printf("%d\n",ans);
    }
    return 0;
}