华为OD机试真题 - 找城市

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int totalCities = scanner.nextInt();

        // 读取城市之间的关系，假设是无向图，且n个城市形成n-1条边
        int[][] cityRelations = new int[totalCities - 1][2];
        for (int i = 0; i < totalCities - 1; i++) {
            cityRelations[i][0] = scanner.nextInt();
            cityRelations[i][1] = scanner.nextInt();
        }

        // 输出最小连通分量中包含的城市编号列表
        System.out.println(findCitiesWithMinimumComponentSize(totalCities, cityRelations));
    }
    
    public static String findCitiesWithMinimumComponentSize(int totalCities, int[][] cityRelations) {
        UnionFindSet[] unionFindSet = new UnionFindSet[cityRelations.length];
        for (int i = 0; i < unionFindSet.length; i++) {
            unionFindSet[i] = new UnionFindSet(totalCities);
        }
        for (int i = 0; i < cityRelations.length; i++) {
            for (int j = 0; j < cityRelations.length; j++) {
                if (cityRelations[j][0] - 1 != i &amp;&amp; cityRelations[j][1] - 1 != i)
                    unionFindSet[i].union(cityRelations[j][0] - 1, cityRelations[j][1] - 1);
            }

        }
        List<Integer> ansList = new ArrayList<Integer>();
        for (int i = 0; i < unionFindSet.length; i++) {
            int[] parent = unionFindSet[i].parent;
            int[] diff = new int[totalCities];
            for (int i1 = 0; i1 < parent.length; i1++) {
                diff[unionFindSet[i].find(parent[i1])] = 1;
            }
            int count = 0;
            for (int j = 0; j < diff.length; j++) {
                if (diff[j] == 1)
                    count++;
            }
            ansList.add(count);
        }
        Collections.sort(ansList);
        String ans = &quot;&quot;;
        for (int i = ansList.size() - 1; i >= 0; i--) {
            if (ansList.get(i) == ansList.get(ansList.size() - 1))
                ans += i + &quot; &quot;;
            else break;
        }
        return ans.substring(0, ans.length() - 1);
    }

    // 并查集类保持不变，因为它已经足够清晰和高效
    static class UnionFindSet {
        int[] parent;

        public UnionFindSet(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot != yRoot) {
                parent[yRoot] = xRoot;
            }
        }
    }