华为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

输出描述

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

用例

输入

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

题目解析

用例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 

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024华为OD机试卷题 文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。

全部评论

相关推荐

05-05 21:45
已编辑
广州大学 Java
点赞 评论 收藏
分享
头像
04-17 09:29
已编辑
湖南农业大学 后端
睡姿决定发型丫:本硕末9也是0offer,简历挂了挺多,只有淘天 美团 中兴给了面试机会,淘天二面挂,美团一面kpi面,中兴一面感觉也大概率kpi(虽然国企,但一面0技术纯聊天有点离谱吧)
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务