找城市 - 华为OD统一考试

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

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

城市与城市之间的道路都不会成环。

当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，

设城市 i 的聚集度为 $D{P}_i$ (Degree of Polymerization) ，$D{P}_i$ = max (城市群 1 的城市个数，城市群2的城市个数，…城市群m的城市个数）。

请找出地图上 DP 值最小的城市（即找到城市 j，使得$D{P}_j$ = min(DP_1,DP_2,…,DP_n)

提示：如果有多个城市满足条件，这些城市都要找出来（可能存在多个解）

提示：$D{P}_i$的计算，可以理解为已知一棵树，删除某个节点后，生成的多个子树，求解多个子树节点数的问题。

输入描述

每个样例：第一行有一个整数 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

题解

解题思路：

1. 构建图：使用邻接表表示图。
2. 遍历每个城市，计算切断通往该城市的所有道路后，生成的城市群的聚集度。
3. 找到聚集度最小的城市，输出结果。

代码大致描述：

1. 构建图：使用邻接表表示图，根据输入的边信息建立城市之间的连接关系。
2. 遍历每个城市：使用 DFS 遍历每个城市，计算切断通往该城市的所有道路后，生成的城市群的聚集度。
3. 找到聚集度最小的城市：比较每个城市的聚集度，找到最小的聚集度，记录对应的城市。
4. 输出结果：按照编号升序输出最小聚集度的城市。

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机试面试交流群（每日真题分享）： 加V时备注“华为od加群”

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏