POJ 3352 Road Construction(边双连通分量)

POJ 3352 Road Construction(边双连通分量)

http://poj.org/problem?id=3352

题意:给你一个连通的无向图,现在问你最少在该图中添加几条边,能使得该图变成边双连通图?

分体:解题思路参考以下博客:

http://blog.csdn.net/lyy289065406/article/details/6762370

首先如果该图本身就是一个边双连通图,我们就不需要添加边了.所以我们先要对该无向图用tarjan()函数求出图中所有的桥.

对于每个桥来说,它都是连接着两个不同的边双连通分量的.(尽管可能一个点也算是一个边双连通分量).对于同一个边双连通分量,我们有以下结论:low[i]值相同的点必定属于同一个边双连通分量.

且我们如果要添加一条边,我们必然在分别属于不同边双连通分量的两个点之间添加.我们如果在同一个边双连通分量内加边,没有任何意义.所以我们把求得所有桥之后的图简化:我们把每个边双连通分量看出一个缩点,然后用每条桥去连接每个缩点(即每个边双连通分量).如下例所示:

所以我们只需要在G图的缩点树上添加边使其变成一个边双连通图即可.这样操作我们能保证我们添加的边最少且最后的图是全局边双连通的.

那么我们对于一棵树需要添加几条边才能使得它变成边双连通的呢?

有以下结论:对于一棵无向树,我们要使得其变成边双连通图,需要添加的边数 == (树中度数为1的点的个数+1)/2

(以上结论不太好证明)

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
int n,m;
vector<int> G[maxn];
int dfs_clock;
int pre[maxn],low[maxn];
int degree[maxn];
int tarjan(int u,int fa)
{
    int lowu=pre[u]=++dfs_clock;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa) continue;
        if(!pre[v])
        {
            int lowv=tarjan(v,u);
            lowu=min(lowu,lowv);
        }
        else if(pre[v]<pre[u])
            lowu=min(lowu,pre[v]);
    }
    return low[u]=lowu;
}
int main()
{
    scanf("%d%d",&n,&m);
    dfs_clock=0;
    memset(pre,0,sizeof(pre));
    memset(degree,0,sizeof(degree));
    for(int i=1;i<=n;i++) G[i].clear();
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    tarjan(1,-1);//得出所有节点的low值,每个不同的low值代表一个边双连通分量
    for(int u=1;u<=n;u++)//遍历每条边
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(low[u]!=low[v]) degree[low[v]]++;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)if(degree[i]==1)
        cnt++;
    printf("%d\n",(cnt+1)/2 );
}