大厂算法：寻找最优的路测线路

一、题目

一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。

当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，设该城市i的聚集度为DPi（Degree of Polymerization）。

DPi = max（城市群1的城市个数，城市群2的城市个数，…城市群m 的城市个数）。

请找出地图上DP值最小的城市（即找到城市j，使得DPj = min(DP1,DP2 … DPn))

提示：

1. 如果有多个城市都满足条件，这些城市都要找出来（可能存在多个解）
2. DPi的计算，可以理解为已知一棵树，删除某个节点后；生成的多个子树，求解多个子数节点数的问题。

二、输入

每个样例：第一行有一个整数N，表示有N个节点。1 <= N <= 1000。

接下来的N-1行每行有两个整数x，y，表示城市x与城市y连接。1 <= x, y <= N

三、输出

输出城市的编号。如果有多个，按照编号升序输出。

四、示例

示例一

输入：
5
1 2
2 3
3 4
4 5

输出：
3

说明：对于城市3，切断通往3的所有道路后，形成2个城市群[（1，2），（4，5）]，其聚集度分别都是2。DP3 = 2。对于城市4，切断通往城市4的所有道路后，形成2个城市群[（1，2，3），（5）]，DP4 = max（3，1）= 3。依次类推，切断其它城市的所有道路后，得到的DP都会大于2，因为城市3就是满足条件的城市，输出是3。

示例二

输入：
6
1 2
2 3
2 4
3 5
3 6

输出：
2 3

说明：将通往2或者3的所有路径切断，最大城市群数量是3，其他任意城市切断后，最大城市群数量都比3大，所以输出2 3

五、题解

1. 本题求解图中去掉一个节点后，计算图中连通分量大小的最大值；所有节点最大值的最小值对应的节点就是答案
2. 划分连通分量和求解连通分量大小通过并查集UnionFind 比较好理解；依次去掉每一个节点，构建并查集并更新最小值即可

5.1 Java 实现

package org.stone.study.algo.ex202412;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class OptimalRoad {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        int[][] grid = new int[n-1][2];
        for(int i = 0; i < n - 1; i++) {
            String[] strs = sc.nextLine().split(" ");
            // 以 1 开始的节点转化为以 0 开始的
            grid[i][0] = Integer.parseInt(strs[0]) - 1;
            grid[i][1] = Integer.parseInt(strs[1]) - 1;
        }

        List<Integer> ans = new OptimalRoad().getMinRoad(n, grid);
        // 打印列表并以空格分隔
        for (int num : ans) {
            System.out.print(num + " ");
        }
    }

    // 每次去掉一个节点，剩下节点加入并查集，找并查集中最大的集合；
    // 所有节点中最小的集合即为答案
    private List<Integer> getMinRoad(int n, int[][] grid) {
        int minDp = Integer.MAX_VALUE;
        List<Integer> ans = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            UnionFind uf = new UnionFind(n);
            for(int[] pair : grid) {
                int x = pair[0], y = pair[1];
                if(x != i && y != i) {
                    uf.union(x, y);
                }
            }

            if(minDp > uf.getMaxSize(n)) {
                minDp = uf.getMaxSize(n);
                ans.clear();
                ans.add(i + 1); // 索引以 0 开始，题目中索引以 1 开始
            } else if(minDp == uf.getMaxSize(n)) {
                ans.add(i + 1); // 索引以 0 开始，题目中索引以 1 开始
            }
        }

        return ans;
    }

    // 并查集
    static class UnionFind {
        int n;
        int[] parent;
        int[] size;

        public UnionFind(int n) {
            this.n = n;
            this.parent = new int[n];
            this.size = new int[n];
            for(int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int find(int x) {
            if(parent[x]!= x) {
                parent[x] = find(parent[x]);
            }

            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY) {
                return;
            }

            parent[rootX] = rootY;
            size[rootY] += size[rootX];
            --n;
        }

        // 这里参数 n 和并查集中的 n 不一样。并查集中的 n 表示合并后集合的个数，但是不能直接知道剩下集合的根节点
        // 这里需要知道所有集合中最大大小的集合
        public int getMaxSize(int n) {
            int maxSize = 1;
            for(int i = 0; i < n; i++) {
                maxSize = Math.max(maxSize, size[i]);
            }

            return maxSize;
        }
    }
}

5.2 Python实现

# 并查集
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, x):
        if self.parent[x]!= x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x!= root_y:
            if self.size[root_x] < self.size[root_y]:
                root_x, root_y = root_y, root_x
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]

    def get_max_size(self):
        return max(self.size)

# 依次去掉每一个节点，求剩下节点的最大连通分量的大小；
# 取所有最大连通分量的最小值
def find_min_dp(n, edges):
    minDp = n
    res = []
    for i in range(n):
        uf = UnionFind(n)
        for x, y in edges:
            # 去掉节点 i
            if x!= i and y!= i:
                uf.union(x, y)

        # 找到最大连通分量的大小
        dpMax = uf.get_max_size() 
        # 更新答案（最大连通分量最小）
        if dpMax < minDp:
            minDp = dpMax
            res = [i + 1]
        elif dpMax == minDp:
            res.append(i + 1)

    return res

if __name__ == '__main__':
    n = int(input())

    edges = []
    for i in range(n - 1):
        x, y = map(int, input().split())
        edges.append((x - 1, y - 1))
    
    res = find_min_dp(n, edges)
    print(' '.join(map(str, res)))