华为OD统一考试 - 找城市

题目描述

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

输出描述

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

用例

题目解析

用例1的意思如下：

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

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

因此DP3最小，输出DP3的3。

用例2图示如下

输出2，3。

通过上面两个示例的图示可以发现，其实本题就是求解：图的连通分量。

本题的难点在于，分量关系没有直接给出，需要我们自己推导，其次是需要我们统计出每个连通分量的节点个数。

比如，上面且1的所有联系，则会产生两个连通分量，分别是[1], [4,2,3,5,6]，这两个连通分量的节点个数分别为1，5。

求解图的连通分量，我们一般使用并查集。

但是，这里我们不能直接根据输入的连接关系，来产生并查集，因为输入的连接关系没有被切断。

本题是要我们尝试切断每一个城市的连接，因此我们遍历出每一个城市，比如城市2，然后遇到和城市2相关的连接后，我们就跳过并查集的合并操作，这样就能产生切断效果。

我们模拟下用例2

初始时，每个城市的父都是自己

输入的连接关系如下

1 2

2 3

2 4

3 5

3 6

现在我们要切断城市2的所有联系，则遇到和2相关的连接时就不进行合并操作

因此上述连接关系只需要考虑

3 5

3 6

这样的话，最终并查集的合并结果为

可以发现，父为3的连通分量具有最多城市数量

这样的话，我们就可以求解出每个DPi了，最后求其中最小的DP对应i即可。

import Foundation

func ODTest_2_27() {
    print("输入描述")
    print("每个样例：第一行有一个整数N，表示有N个节点。1 <= N <= 1000。")
    print("接下来的N-1行每行有两个整数x，y，表示城市x与城市y连接。1 <= x,  y <= N")
    let N = Int(readLine() ?? "") ?? 0
    var