找城市

题目描述

一张地图上有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

题解

解题思路：

1. 构建图：使用邻接表表示图。

2. 遍历每个城市，计算切断通往该城市的所有道路后，生成的城市群的聚集度。

3. 找到聚集度最小的城市，输出结果。

代码大致描述：

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

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;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

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