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

思路：以每个点进行dfs，求子节点的所以路线，求出最大值，然后再求出每个点的最大值找最小值。

图中以根节点的每个子节点j进行dfs，得到根节点的值为5