华为od-C卷200分题目2

华为od-C卷200分题目2 - 找城市

2024-06-16 23:20

文章标签 题目 200 华为城市 od

本文主要是介绍华为od-C卷200分题目2 - 找城市，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

华为od-C卷200分题目2 - 找城市

题目描述

一个城市规划问题，一个地图有很多城市，两个城市之间只有一种路径，切断通往一
个城市i的所有路径之后，其他的城市形成了独立的城市群，这些城市群里最大的城
市数量，就是聚集度DPi，现在给出一个地图上各个城市的路径，输出聚集度最小的
城市，如果有多个结果，按照编号从小到大输入描述
第一行输入 城市节点数目N
后面N-1输入城市之间的路径输出描述
聚集度最小的城市示例
输入
5
1 2
2 3
3 4
4 5
输出
3
说明
将通往3的所有路径切断，最大城市群数量是2，其他任意城市切断后，最大城市群
数量都比2大，所以输出3
1
输入
6
1 2
2 3
2 4
3 5
3 6
输出
2 3
说明
将通往2或者3的所有路径切断，最大城市群数量是3，其他任意城市切断后，最大
城市群数量都比3大，所以输出2

import java.util.*;public class Main {static HashMap<Integer, List<Integer>> map;public static void main(String[] args) {int n, a, b;Scanner sc = new Scanner(System.in);n = sc.nextInt();int[] nums = new int[n + 1];map = new HashMap<>();for (int i = 1; i < n; i++) {a = sc.nextInt();b = sc.nextInt();save(a, b);save(b, a);}int max = Integer.MAX_VALUE;TreeSet<Integer> result = new TreeSet<>();HashSet<Integer> set = new HashSet<>();for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {Integer key = entry.getKey();set.add(key);for (Integer i : entry.getValue()) {nums[key] = Math.max(nums[key], dfs(i, set));}if (nums[key] < max) {result.clear();result.add(entry.getKey());max = nums[key];}else if (nums[key] == max) {result.add(entry.getKey());}set.clear();}for (Integer i : result) {System.out.printf(i + " ");}System.out.println();}public static void save(int a, int b) {if (map.containsKey(a)) {map.get(a).add(b);} else {LinkedList<Integer> list = new LinkedList<>();list.add(b);map.put(a, list);}}public static int dfs(int i, HashSet<Integer> set) {Stack<Integer> stack = new Stack<>();int sum = 0;stack.push(i);while (!stack.isEmpty()) {sum++;Integer pop = stack.pop();set.add(pop);for (Integer temp : map.get(pop)) {if (!set.contains(temp)) {stack.push(temp);}}}return sum;}
}