找城市 - 华为OD统一考试（D卷）
OD统一考试（C卷）
分值： 200分
题解： Java / Python / C++
题目描述
一张地图上有n 个城市，城市和城市之间有且只有一条道路相连：要么相连，要么通过其它城市中转相连（可中转一次或多次）。
城市与城市之间的道路都不会成环。
当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，
设城市 i 的聚集度为 (Degree of Polymerization) ，
= max (城市群 1 的城市个数，城市群2的城市个数，...城市群m的城市个数）。
请找出地图上 DP 值最小的城市（即找到城市 j，使得 = min(DP_1,DP_2,...,DP_n)
提示：如果有多个城市满足条件，这些城市都要找出来（可能存在多个解）
提示：的计算，可以理解为已知一棵树，删除某个节点后，生成的多个子树，求解多个子树节点数的问题。
输入描述
每个样例：第一行有一个整数 N，表示有 N个节点， 1≤N≤1000
接下来的 N−1 行每行有两个整数 x，y，表示城市 x 与城市 y 连接，1≤x,y≤N
输出描述
输出城市的编号，如果有多个，按照编号的升序输出
示例1
输入：
5
1 2
2 3
3 4
4 5
输出：
3
说明：
输入表示的是如下地图。
切断通往 3 的所有道路后，形成 2 个城市群，[(1,2),(4,5)]，其聚集度分别是 2,2, dp2 = 2；
切断通往 4 的所有道路后，形成 2 个城市群，[(1,2,3),(5)]，其聚集度分别是 3,1, dp3 = 3；
依次类推，切断其它城市的所有道路后，得到的 DP 都会大于2，因为城市 3 就是满足条件的城市，输出的是 3。
示例2
输入：
6
1 2
2 3
2 5
3 4
3 6
输出：
2 3
说明：
将通往2或者3的所有路径切断，最大城市群数量是3，其他任意城市切断后，最大城市群数量都比3大，所以输出2 3
题解
解题思路：
构建图：使用邻接表表示图。
遍历每个城市，计算切断通往该城市的所有道路后，生成的城市群的聚集度。
找到聚集度最小的城市，输出结果。
代码大致描述：
- 构建图：使用邻接表表示图，根据输入的边信息建立城市之间的连接关系。
- 遍历每个城市：使用 DFS 遍历每个城市，计算切断通往该城市的所有道路后，生成的城市群的聚集度。
- 找到聚集度最小的城市：比较每个城市的聚集度，找到最小的聚集度，记录对应的城市。
- 输出结果：按照编号升序输出最小聚集度的城市。
Java
import java.util.*;
/**
* @author code5bug
*/
public class Main {
static Map<Integer, List<Integer>> g = new HashMap<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 构建图
int n = scanner.nextInt();
for (int i = 1; i < n; i++) {
int x = scanner.nextInt(), y = scanner.nextInt();
g.computeIfAbsent(x, p -> new ArrayList<>()).add(y);
g.computeIfAbsent(y, p -> new ArrayList<>()).add(x);
}
List<Integer> cities = new ArrayList<>();
// 地图上最小的 DP 值
int minDp = Integer.MAX_VALUE;
for (int i : g.keySet()) {
int dpi = 0; // 城市i 的聚集度
for (int neighbor : g.get(i)) {
dpi = Math.max(dpi, getChildNodes(neighbor, i));
}
if (dpi < minDp) { // 找到地图上更小的 DP 值
minDp = dpi;
cities = new ArrayList<>();
cities.add(i);
} else if (dpi == minDp) {
cities.add(i);
}
}
Collections.sort(cities);
for (int city : cities) {
System.out.print(city + " ");
}
}
// 求fa为父节点 cur 为根的子树的节点数
static int getChildNodes(int cur, int fa) {
int cnt = 1;
for (int neighbor : g.get(cur)) {
if (neighbor != fa) {
cnt += getChildNodes(neighbor, cur);
}
}
return cnt;
}
}
Python
from collections import defaultdict
from math import inf
g = defaultdict(list)
# 构建图
n = int(input())
for _ in range(n - 1):
x, y = map(int, input().split())
g[x].append(y)
g[y].append(x)
def getChildNodes(cur: int, fa: int) -> int:
""" 返回fa为父节点 cur 为根的子树的节点数"""
cnt = 1
for neighbor in g[cur]:
if neighbor != fa:
cnt += getChildNodes(neighbor, cur)
return cnt
# dp 值最小的城市， 结果
min_dp, cities = inf, []
for i in g.keys():
dpi = max([getChildNodes(u, i) for u in g[i]])
if dpi < min_dp:
min_dp = dpi
cities = [i]
elif dpi == min_dp:
cities.append(i)
cities.sort()
print(*cities)
C++
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// 声明全局变量
map<int, vector<int>> g;
// 求fa为父节点 cur 为根的子树的节点数
int getChildNodes(int cur, int fa) {
int cnt = 1;
for (int neighbor : g[cur]) {
if (neighbor != fa) {
cnt += getChildNodes(neighbor, cur);
}
}
return cnt;
}
int main() {
// 构建图
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> cities;
// 地图上最小的 DP 值
int minDp = INT_MAX;
for (auto &entry : g) {
int i = entry.first;
int dpi = 0; // 城市i的聚集度
for (int neighbor : entry.second) {
dpi = max(dpi, getChildNodes(neighbor, i));
}
if (dpi < minDp) { // 找到地图上更小的 DP 值
minDp = dpi;
cities = {i};
} else if (dpi == minDp) {
cities.push_back(i);
}
}
sort(cities.begin(), cities.end());
for (int city : cities) {
cout << city << " ";
}
return 0;
}
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
#华为od##华为od题库##华为od机试##华为机试##华为OD机试算法题库#
投递腾讯云智研发等公司7个岗位