一、题目
一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。
当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，设该城市i的聚集度为DPi（Degree of Polymerization）。
DPi = max（城市群1的城市个数，城市群2的城市个数，…城市群m 的城市个数）。
请找出地图上DP值最小的城市（即找到城市j，使得DPj = min(DP1,DP2 … DPn))
提示：
- 如果有多个城市都满足条件，这些城市都要找出来（可能存在多个解）
- 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
五、题解
- 本题求解图中去掉一个节点后，计算图中连通分量大小的最大值；所有节点最大值的最小值对应的节点就是答案
- 划分连通分量和求解连通分量大小通过并查集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)))