【华为机试】2023年真题B卷(python)-城市聚集度

发布时间:2023年12月22日

一、题目

题目描述:

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

输入输出示例仅供调试,后台判题数据一般不包含示例
输入:
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。
示例2???

输入输出示例仅供调试,后台判题数据一般不包含示例
输入:
6

1 2

2 3

2 4

3 5

3 6
输出:
2 3
说明:
将通往2或者3的所有路径切断,最大城市群数量是3,其他任意城市切断后,最大城市群数量都比3大,所以输出2 3。

四、要求

时间限制:C/C++ 1秒,其他语言 2秒
空间限制:C/C++262144K,其他语言524288K

五、参考代码?

# -*- coding: utf-8 -*-

class UF:
    def __init__(self, n=0):
        self.count = n
        self.N = n
        self.id = [0 for x in range(n+1)]
        self.sz = [0 for x in range(n+1)]
        for i in range(1, n+1):
            self.id[i] = i
            self.sz[i] = 1
 
    def getMax(self):
        max_val = 0
        for i in range(1, self.count+1):
            max_val = max(max_val, self.sz[i])
        return max_val

    def union (self, p, q):
        pRoot = self.find(p)
        qRoot = self.find(q)
        if (pRoot != qRoot):
            if (self.sz[pRoot] < self.sz[qRoot]) :
                self.id[pRoot] = qRoot
                self.sz[qRoot] += self.sz[pRoot]
            else:
                self.id[qRoot] = pRoot
                self.sz[pRoot] += self.sz[qRoot]
            self.count-=1
        
    def find (self, p) :
        if (p == self.id[p]) :
            return p
        self.id[p] = self.find(self.id[p])
        return self.id[p]
    


n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(x) for x in input().split(" ")])
res = float('inf')
maxArray = [0 for i in range(n + 1)]; #统计每个城市的聚集度
for i in range(1, n+1):  # 对于每一个城市
    uf = UF(n);
    for j in range(n-1):  # 判断每一条路径
        if (arr[j][0] == i or arr[j][1] == i):
            continue
        else:
            uf.union(arr[j][0], arr[j][1])
    maxArray[i] = uf.getMax();  # 每个城市对应的聚集度
    res = min(res, maxArray[i]);  # 切掉路径后的最小聚集度
res_str = ""
for i in range(1, len(maxArray)):
    if (maxArray[i] == res):
        res_str += str(i) + " "
print(res_str[:-1])
文章来源:https://blog.csdn.net/u014481728/article/details/135142786
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。