首页 > 搜索 > DFS搜索 > HDU 4587-TWO NODES-图-[解题报告]HOJ
2015
09-17

HDU 4587-TWO NODES-图-[解题报告]HOJ

TWO NODES

问题描述 :

Suppose that G is an undirected graph, and the value of stab is defined as follows:
Play the Dice

Among the expression,G-i, -j is the remainder after removing node i, node j and all edges that are directly relevant to the previous two nodes. cntCompent is the number of connected components of X independently.
Thus, given a certain undirected graph G, you are supposed to calculating the value of stab.

输入:

The input will contain the description of several graphs. For each graph, the description consist of an integer N for the number of nodes, an integer M for the number of edges, and M pairs of integers for edges (3<=N,M<=5000).
Please note that the endpoints of edge is marked in the range of [0,N-1], and input cases ends with EOF.

输出:

The input will contain the description of several graphs. For each graph, the description consist of an integer N for the number of nodes, an integer M for the number of edges, and M pairs of integers for edges (3<=N,M<=5000).
Please note that the endpoints of edge is marked in the range of [0,N-1], and input cases ends with EOF.

样例输入:

4 5
0 1
1 2
2 3
3 0
0 2

样例输出:

2

题意:给出一个无向图,删除两个点让剩余的图的连通分量的数量最大。

思路:考虑每一个点,尝试将其删除,然后计算剩余的连通分量的个数,对于每个连通分量,再求删除某一个点所能增加的最多的连通分量的数量。对于第一步,直接标记一下要删除的点,然后dfs计算一下连通分量的个数即可,对于第二歩,如果再一个一个删肯定要超时了,由于要在一个连通分支中删除一个点,那么这个点要尽可能是割点,可以考虑一下求割点的过程,用tarjan求割点的时候,当lowv>=pre[u]的时候,则说明u是割点,画个图的话应该能理解好一些,没当遇到这种情况,那么删除u的时候,就会增加一个连通分量,这样的话就可以在求割点的时候计算出删除这个割点会增加多少连通分量了,这样的话,答案就能计算出来了,另外还有一些特殊情况需要特判,比如一个连通分支中没有割点的情况。

 

代码:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=5000+10;
int pre[maxn],vis[maxn],dfs_clock;
int ans,ban,total,step,n,m,temp;
vector<int>G[maxn];
int tarjan(int u,int fa)
{
    bool iscut=false;
    int child=0,cutnum=0;
    int lowu=pre[u]=++dfs_clock;
    for(int i=0;i<G[u].size();++i)
    {
        int v=G[u][i];
        if(v==ban) continue;
        if(!pre[v])
        {
            child++;
            int lowv=tarjan(v,u);
            lowu=min(lowu,lowv);
            if(lowv>=pre[u])
            {
                iscut=true;
                cutnum++;
            }
        }
        else if(pre[v]<pre[u]&&v!=fa)
           lowu=min(lowu,pre[v]);
    }
    if(fa<0&&child==1) iscut=false;
    if(child==0&&fa==-1) ans=max(ans,total-1);
    if(iscut)
      ans=max(ans,total+cutnum-(int)(fa==-1));
    return lowu;
}
void dfs(int u)
{
    temp++;
    vis[u]=step;
    for(int i=0;i<G[u].size();++i)
    {
        int v=G[u][i];
        if(vis[v]!=step&&v!=ban)
           dfs(v);
    }
}
void find_conn(int x)
{
    step++;
    total=0;
    ban=x;
    bool flag=false;
    for(int i=0;i<n;++i)
    {
        if(vis[i]!=step&&i!=ban)
        {
            temp=0;
            dfs(i);
            total++;
            if(temp>=2) flag=true;
        }
    }
    if(flag) ans=max(ans,total);
    memset(pre,0,sizeof(pre));
    dfs_clock=0;
    for(int i=0;i<n;++i)
      if(!pre[i]&&i!=ban) tarjan(i,-1);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(~scanf("%d%d",&n,&m))
    {
        int a,b;
        for(int i=0;i<n;++i) G[i].clear();
        for(int i=0;i<m;++i)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        memset(vis,0,sizeof(vis));
        ans=0;step=0;
        for(int i=0;i<n;++i)
           find_conn(i);
        printf("%d\n",ans);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/qian99/article/details/10034775


, ,