本文主要是介绍华为OD机试【城市聚集度】(java)(200分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1、题目描述
一张地图上有N个城市,城市和城市之间有且只有一条道路相连,要么直接相连,要么通过其他城市中转相连(可中转一次或多次)。城市与城市之间的道路都不会成环。
当切断通往某城市i的所有道路后,地图上将分成多个连通的城市群,设该城市i的聚集度为DPi of Polymerization), DPi = max(城市群1的城市个数,城市群2的城市个数,…城市群m的城市个数)。 请找出地图上DP值最小的城市(即找到城市j,使得DPj = min(DP1,DP2…DPn))。
提示:如果有多个城市都满足条件,这些城市都要找出来(可能存在多个解)。
提示:DPi的计算,可以理解为已知一个树,删除某个节点后,生成的多个字树,求解多个字树节点数的问题。
2、输入描述
每个样例,第一行有一个整数N,表示有N个节点,1 <=N <=1000
j接下来的N-1行每行有两个整数x,y,表示城市x与城市y连接。1 <= x , y <= N
3、输出描述
输出城市的编号,如果有多个,按照编号升序输出。
用例:
输入
5
1 2
2 3
3 4
4 5输出
3ps:
对于城市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。
温馨提示!!!
华为OD机试考试官方会对考生代码查重。华为od机试因为有题库所以有很大的概率抽到原题。如果碰到了题库中的原题,千万不要直接使用题解中的代码,一定要做些修改,比如代码中的变量名,除此之外,代码的组织结构和逻辑也要进行一些改变,所以在日常的刷题中,要提前编写好属于自己的代码。
4、题解
遍历每个城市作为基准,初始化并查集将与基准城市相连边删除,定义map,key:连通块,value:连通块大小,定义最大联通块大小,如果当前最大连通块大小比之前的最小值还小,则更新最小值和最小值所在的城市,如果当前最大连通块大小与之前的最小值相等,则将城市加入最小值所在的城市列表。
代码如下:
public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.parseInt(sc.nextLine());int[][] arr = new int[n-1][2];for (int i=0; i<n-1; i++) {arr[i] = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();}// 最小的最大连通块int min = Integer.MAX_VALUE;// 最小的最大连通块所在城市List<Integer> citys = new ArrayList<>();for (int i=1; i<n+1; i++) {FindUnionSet fun = new FindUnionSet(n+1);// 将与特殊城市相连的边删除for (int[] relation : arr) {int x = relation[0];int y = relation[1];if (x == i || y == i) {continue;}fun.unionSet(x, y);}// 连通块 连通块大小Map<Integer, Integer> maps = new HashMap<>();for (int father : fun.fatherArr) {father = fun.find(father);maps.put(father, maps.getOrDefault(father, 0) + 1);}int max = 0;for (Map.Entry<Integer, Integer> entry : maps.entrySet()) {max = Math.max(max, entry.getValue());}if (max < min) {min = max;citys.clear();citys.add(i);}else if (max == min) {citys.add(i);}}for (int city : citys) {System.out.print(city + " ");}
}static class FindUnionSet {// 每个节点父节点private int[] fatherArr;public FindUnionSet(int n) {fatherArr = new int[n];for (int i=0; i<n; i++) {fatherArr[i] = i;}}public int find(int x) {if (fatherArr[x] != x) {fatherArr[x] = find(fatherArr[x]);}return fatherArr[x];}// 合并x y所在集合public void unionSet(int x, int y) {int x_father = find(x);int y_father = find(y);// 若 x y不在同一集合,则将y的祖先节点设置为x的祖先节点if (x_father != y_father) {fatherArr[y_father] = x_father;}}
}
执行结果如下:
这篇关于华为OD机试【城市聚集度】(java)(200分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!