POJ 3352 Road Construction 题解【tarjan】【割边/桥】

点击量：575

这个题和洛谷P3225 矿场搭建比较相似，不过这个题影响的是边，而不是点，所以有所变化。

目录

Description

It’s almost summer time, and that means that it’s almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.

 

The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.

 

Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.

 

So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.

 

Input

The first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.

 

Output

One line, consisting of an integer, which gives the minimum number of roads that we need to add.

 

Sample Input 1

10 12

1 2

1 3

1 4

2 5

2 6

5 6

3 7

3 8

7 8

4 9

4 10

9 10

Output for Sample Input 1

2

 

Sample Input 2

3 3

1 2

2 3

1 3

Output for Sample Input 2

0

题目大意

   有一个岛上有$ n\in [3,1000] $个景点，通过$ m\in [2,1000]$条双向边连接着。这其中的路有时会维修，此时两个方向都走不了。问需要添加多少条边，使得无论哪条路维修时，任意两个景点都可以互相到达。输入数据保证是连通图。

   和矿场搭建那个题【解题报告】比起来，这个题维修的是边，这意味着边所连接的两个点可以被经过，但维修的边不能被经过。对于一个边双连通分量，删除其中任意一条边是没有影响的。有影响的是当删除割边，也就是桥时，原来的连通图会被分成两个不连通的图，这样就不能互相到达了。

   因为图本来是连通图，由于桥的特性，只会让一个连通图变成两个连通图，不会更多。因此我们考虑对于一个连通块，如果它连通外界的割边断了，我们就需要把它连接到外界去，这样就又只有一个连通图了。但问题是，图中可能出现多个这样的连通块，我们要分两种情况。

1.只连接一条割边的连通块/双连通分量

   对于这样的连通块，我们称之为“叶子连通块”，因为它在“缩环为点”后，度为1，也就是只与外界连上了一条边，就像叶子节点一样。如果它的割边断了，它必须连一条边到外界，因为它除了割边没有其他边向外连接，那么它就别无选择。

2.连接两条割边或以上的连通块/双连通分量

   如果这种连通块断了一条割边（最多只可能断一条割边），此时有且仅有两个大连通块，但是它还有其他割边，它可以把自己属于的连通块“旅游”完毕，最后通过一种方式到另一个连通块去，为了使添加的边最少，我们能不加就不加。想到在“叶子连通块”中已经加过边了，而且一个连通块一定可以通过其他割边旅游到一个叶子连通块上，我们就可以以叶子连通块上新加的边通往另一个连通块上。

   此时我们的结论已经出来了。每一个叶子连通块都需要连接一条边到割边以外的连通块去，且每个叶子连通块互不干扰。如果每个叶子连通块至少连一条边，那么因为一条边连接两个点（也就是两个叶子连通块），可以消去两个叶子连通块，所以我们的需求就是叶子连通块个数k除以二并向上取整。即$ \lceil \frac{k}{2} \rceil$。

   求割边的方法在代码中会有较详细注释，文章后面也有介绍。最后对于每个没有遍历的连通块dfs一遍，找出叶子连通块的个数就可以了。

Code：

#include<cstdio>
#include<cstring>
int min(int x,int y){return x<y?x:y;}
struct node
{
    int n;
    node *nxt;
    node (int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node(){nxt=NULL;}
};
node head[1010],*tail[1010];
//tarjan求割边
int dfn[1010],low[1010],cnt=0;
bool bridge[1010][1010];//b[i][j]表示i,j之间的点是否是桥
void dfs(int x,int from)
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(!dfn[p->n])
        {
            dfs(p->n,x);
            low[x]=min(low[x],low[p->n]);//最早能回溯到的点
            //如果p->n不能不通过p这条边回溯到x，那么与x和p->n之间的边去掉是等价的，它就是割边了
            if(low[p->n]>dfn[x])//则x和p->n之间是桥
            {
                bridge[p->n][x]=true;
                bridge[x][p->n]=true;
            }
        }
        else if(p->n!=from)
            low[x]=min(low[x],dfn[p->n]);
    }
}
bool used[1020];
int num;
void Dfs(int x)
{
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(bridge[x][p->n])
        {
            num++;
            continue;
        }
        if(used[p->n])
            continue;

        used[p->n]=true;
        Dfs(p->n);
    }
    return ;
}
int main()
{
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        tail[i]=&head[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        tail[u]->nxt=new node(v);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u);
        tail[v]=tail[v]->nxt;
    }
    memset(bridge,0,sizeof(bridge));
    dfs(1,0);//图是连通的

    memset(used,0,sizeof(used));
    int ans=0;
    for(int i=1;i<=n;i++)
        if(!used[i])
        {
            num=0;
            used[i]=true;
            Dfs(i);
            if(num==1)
                ans++;
        }
    if(ans&1)
        ans++;
    printf("%d\n",ans/2);
    return 0;
}

    对于求割边的解释：我们设v是由u引进的新节点，临时把u->v和v->u的双向边删掉，那么在dfs(v)结束后，没有能回溯到u，那么说明v->u没有另外一条路能到达，u->v就达到了割边的效果，所以它就是割边。