【POJ 3352】Road Construction 题解（Tarjan算法求边双连通分量缩点）-摩杜云开发者社区

描述现在几乎是夏天，这意味着几乎是夏天的施工时间！今年，负责偏远岛热带岛屿天堂道路的好心人希望修复和升级岛上各个旅游景点之间的各种道路。道路本身也很有趣。由于岛上的奇怪风俗，道路的安排使得它们不会在交叉路口相遇，而是通过桥梁和隧道相互交叉或下方。通过这种方式，每条道路在两个特定的旅游景点之间穿行，这样游客就不会无法挽回地迷路。不幸的是，考虑到每条道路所需的维修和升级的性质，当建筑公司在某条道路上施工时，这条道路在任何方向都无法使用。如果无法在两个旅游景点之间旅行，即使建筑公司在任何特定时间只在一条道路上施工，这可能会造成问题。因此，偏远岛屿的公路部门决定请您的咨询服务来帮助解决这个问题。已决定在各个景点之间修建新的道路，以便在最终配置中，如果任何一条道路正在施工，则仍可以使用剩余的道路在任何两个旅游景点之间行驶。您的任务是找到所需的最少数量的新道路。

输入第一行输入由正整数n和r组成，用空格隔开，其中3≤n≤1000是岛上旅游景点的数量，2≤r≤1000是道路的数量。旅游景点的标记很方便，从1到n。以下r行中的每一行将由两个整数v和w组成，用空格隔开，表示标记为v和w的景点之间存在一条道路。请注意，您可以沿着每条道路向任何方向行驶，任何一对旅游景点之间最多只能有一条道路直接连接。此外，您可以放心，在当前配置中，您可以在任意两个旅游景点之间旅行。输出一行，由一个整数组成，它给出了我们需要添加的最小道路数。

Sample Input

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

Sample Input 2 3 3 1 2 2 3 1 3 Sample Output

Output for Sample Input 1 2

Output for Sample Input 2 0 Source

CCC 2007

思路

用Tarjan算法求边双连通分量缩点，每两个度为1的叶子节点添加一条边。

AC代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 100005;

int cnt;
struct Snode {
    int to;
    int next;
}edge[maxn];
int head[maxn];

// tarjan
int num;
int dfn[maxn], low[maxn];
int deg[maxn];

void init(){
    cnt = 0;
    num = 0;
    memset(head, -1, sizeof(head));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(deg, 0, sizeof(deg));
}

void add(int u, int v){
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void print(int x){
    for(int j = 1; j <= x; j++){
        cout << j << "-";
        for(int i = head[j]; ~i; i = edge[i].next){
            cout << edge[i].to;
        }
    cout << endl;
    }
}

void tarjan(int u, int root){
    dfn[u] = low[u] = ++num;
    for (int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if (v == root)
        {
            continue;
        }
        if(!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }else{
            low[u] = min(low[u], dfn[v]);
        }
    }

}

int main() {
    int n, r, si;
    while(cin >> n >> r)
    {
        init();
        for(int i = 0; i < r; i++){
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        // print(r);
        for(int i = 1; i <= r; i++){
            if(!dfn[i]){
                tarjan(i,i);
            }
        }
        // 求缩点和度
        for(int u = 1; u <= n; u++){
            for(int i = head[u]; ~i; i = edge[i].next){
                int v = edge[i].to;
                if(low[u] != low[v]){
                    deg[low[u]]++;
                }
            }
        }
        // 统计叶子数
        int leaf = 0;
        for(int i = 1; i <= n; i++){
            if(1 == deg[i]){
                leaf++;
            }
        }
        // 每两个叶子间加一条路
        cout << (leaf + 1) / 2 << endl;
    }
    return 0;
}