华为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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

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

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