道路施工(缩点,边-双连通分量)

2018-04-25 14:46:07


题目描述

某个企业想把一个热带天堂岛变成旅游胜地,岛上有N个旅游景点,任意2个旅游景点之间有路径连通(注意不一定是直接连通)。而为了给游客提供更方便的服务,该企业要求道路部门在某些道路增加一些设施。

道路部门每次只会选择一条道路施工,在该条道路施工完毕前,其他道路依然可以通行。然而有道路部门正在施工的道路,在施工完毕前是禁止游客通行的。这就导致了在施工期间游客可能无法到达一些景点。

为了在施工期间所有旅游景点依然能够正常对游客开放,该企业决定搭建一些临时桥梁,使得不管道路部门选在哪条路进行施工,游客都能够到达所有旅游景点。给出当下允许通行的R条道路,问该企业至少再搭建几条临时桥梁,才能使得游客无视道路部门的存在到达所有旅游景点?

Input Data

The first line of input will consist of positive integers nn and rr, 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 11 to nn.

Each of the following rr lines will consist of two integers, vv and ww, separated by a space, indicating that a road exists between the attractions labelled vv and ww. 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 Data

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

样例:

输入

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

输出:

2




题解部分

由双连通分量的性质可以知道,双连通分量里删去任何一条边都能连通。所以这题要把所有的双连通分量求出来,再进行缩点建成一个图,统计度为2的边双连通的个数k。答案就是(k+1)/2

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int s[10000],d[10000];
int n,m,cnt=0,tot=0,num=0,p=0;
int head[20010],nxt[20010],to[20010];
int low[1010],pre[1010],f[1010];
void addedge(int x,int y)//邻接表加边
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
void dfs(int u,int fa)
{
    low[u]=pre[u]=++tot;
    s[++p]=u;//扫到的点进站
    for(int i=head[u];i!=-1;i=nxt[i])
    {
        int v=to[i];
        if(!pre[v])
        {
            dfs(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(pre[v]<pre[u] && v!=fa) low[u]=min(low[u],pre[v]);
    }
    if(low[u]==pre[u])
    {
        cnt++;
        do
        {
            f[s[p--]]=cnt;
        }while(s[p+1]!=u && p);//把栈里的点标记为当前的连通分量
    } 
}
int main()
{
    memset(f,0,sizeof(f));
    memset(pre,0,sizeof(pre));
    memset(low,0,sizeof(low));
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    cnt=0;
    for(int i=1;i<=n;i++)
        if(!pre[i]) dfs(i,0);
    for(int i=1;i<=n;i++)
        for(int j=head[i];j!=-1;j=nxt[j])
            if(f[i]!=f[to[j]]) d[f[i]]++,d[f[to[j]]]++;//如果不属于同一个连通分量,i和to[j]所属的连通分量的度加一
    for(int i=1;i<=cnt;i++)
        if(d[i]==2) num++;//统计
    cout<<(num+1)/2;
    return 0;
}