道路建设问题

一 原问题描述

Road Construction - POJ 3352 - Virtual Judgehttps://vjudge.net/problem/POJ-3352

二 输入与输出

1 输入

输入的第 1 行包括正整数 n 和 r，其中 n 是旅游景区点的数量，r 是道路的数量。旅游景点编号为 1 到 n ，以下 r 行中每一行都将由两个整数 v 和 w 组成，表示在 v 和 w 的景点之间存在道路。请注意，道路是双向的，在任何两个旅游景点之间最多有一条道路。此外，在目前的配置中，可以在任意两个旅游景点之间旅行。

2 输出

单行输出需要添加的最少道路数量。

三 输入与输出样例

1 输入样例

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

2 输出样例

Output for Sample Input 1

2

Output for Sample Input 2

0

四 分析

1 不添加边的情况 

输入样例2，构建的图如下。不需要添加新的道路，就可以保证一条道路在维修时，可以通过其他道路到达任何一个景点。因此需要添加0条边。

2 添加多条边的情况

如果在无向图中不存在桥，则称它为边双连通图。如果一个节点在一个边双连通图分量中，则不需要添加边。因此需要求解边双连通分量。在边双连通分量之间需要添加边。针对样例1，其边双连通分量如下图所示。

将每个连通分量缩成一个点，如下图所示

求解需要添加的新路的数量。如果度为 1 的节点为 k，则至少需要填 (k+1)/2 条边。例如，对 3 个度为 1 的节点至少需要加两条边，对 4 个度为1的节点至少需要添加两条边。

为什么要统计叶子（度为1的节点）呢？连通分量缩点得到一棵树，在树中任意两个点之间添加一条边都会产生一个回路。在两个叶子之间添加一条边，则叶子和一些分支节点一起构成一个回路。而在分支节点之间添加一条边，产生的回路不会包含叶子。因此通过连接叶子可以添加最少的边，使得每个节点都在回路中。

为什么添加的边数为(k+1)/2呢？这要分度为1的节点的个数是奇数还是偶数，如果是偶数，则是 k/2,如果是奇数，则是(k+1)/2，因此统一为(k+1)/2。

五 算法设计

1 先运行 Tarjan 算法，求解边双连通分量。

2 缩点。检查每个节点 u 的每个邻接点 v,若 low[u]!=low[v],则将这个连通分量点 low[u] 的度加1，degree[low[u]]++，同一个连通分量中的节点 low值相等。

3 统计度为 1 的点的个数为，即叶子节点的个数，添加的最少边为(leaf+1)/2。

六 代码

package graph.poj3352;

import java.util.Scanner;

public class POJ3352 {
    static final int maxn = 1000 + 5;
    static int n;
    static int m;
    static int head[];
    static int cnt;
    static int root;
    static int low[];
    static int dfn[];
    static int degree[]; // 节点的度
    static int num;

    static Edge e[] = new Edge[maxn << 1];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    static void add(int u, int v) { // 添加一条边u--v
        e[++cnt].next = head[u];
        e[cnt].to = v;
        head[u] = cnt;
    }

    /**
     * 功能描述：tarjan 算法
     *
     * @param u  起始节点
     * @param fa 起始节点的父节点
     * @author cakin
     * @date 2022/7/3
     */
    static void tarjan(int u, int fa) { // 求边双连通分量
        dfn[u] = low[u] = ++num;

        for (int i = head[u]; i != 0; i = e[i].next) {
            int v = e[i].to;
            if (v == fa)
                continue;
            if (dfn[v] == 0) {
                tarjan(v, u);
                low[u] = Math.min(low[u], low[v]);
            } else
                low[u] = Math.min(low[u], dfn[v]);
        }
    }

    static void init() {
        head = new int[maxn];
        low = new int[maxn];
        dfn = new int[maxn];
        degree = new int[maxn];
        cnt = num = 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            init();
            int u, v;
            while (m-- != 0) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                add(u, v);
                add(v, u);
            }
            tarjan(1, 0);
            for (u = 1; u <= n; u++)
                for (int i = head[u]; i != 0; i = e[i].next) {
                    v = e[i].to;
                    if (low[u] != low[v])
                        degree[low[u]]++;
                }
            int leaf = 0;
            for (int i = 1; i <= n; i++)
                if (degree[i] == 1)
                    leaf++;
            System.out.println((leaf + 1) / 2);
        }
    }
}

class Edge {
    int to;
    int next;
}

七 测试