华为机考笔试题 找城市_找个一条尽可能长的访问路径 地图上有100个城市,前20个城市为必须访问的城市,

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

我采用了并查集的方法解题，循环n次遍历所有城市的结果，每个城市遍历所有的链接信息，如果出现当前循环需要排除的城市，则不执行本次合并操作。

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int i, j;
        int[] xPos = new int[n];
        int[] yPos = new int[n];
        for (i=1; i<n; i++) {
            xPos[i] = scanner.nextInt();
            yPos[i] = scanner.nextInt();
        }
        if (n == 1) {
            System.out.println(1);
        } else if (n == 2) {
            System.out.println(1);
            System.out.println(2);
        } else {
            sortPos(xPos, yPos, n);
            int min = 1005;
            int max;
            int totalCity;
            List<Integer> minCityList = new ArrayList<>();
            for (i = 1; i <= n; i++) {
                CityNode[] cityNodes = new CityNode[n + 1];
                max = 0;
                // 初始化cityNodes
                for (j = 1; j <= n; j++) {
                    cityNodes[j] = new CityNode(j);
                }
                for (j = 1; j < n; j++) {
                    // 被剔除city关系不处理
                    if (xPos[j] == i || yPos[j] == i) {
                        continue;
                    }
                    CityNode yCity = cityNodes[yPos[j]];
                    CityNode xCity = cityNodes[xPos[j]];
                    // 如果xCity不是根，xCity找到根
                    if (xCity.parent != xCity.val) {
                        xCity = cityNodes[xCity.parent];
                    }
                    if (yCity.parent == yCity.val) {
                        mergeCity(xCity, yCity);
                    } else {
                        CityNode yCityParent = cityNodes[yCity.parent];
                        mergeCity(xCity, yCityParent);
                    }
                }
                for (j = 1; j <= n; j++) {
                    if (cityNodes[j].parent == cityNodes[j].val) {
                        totalCity = cityNodes[j].children.size() + 1;
                        max = max < totalCity ? totalCity : max;
                    }
                }
                if (min > max) {
                    min = max;
                    minCityList.clear();
                    minCityList.add(i);
                } else if (min == max) {
                    minCityList.add(i);
                }
            }
            minCityList.forEach(item -> System.out.println(item));
        }
    }
 
    private static void mergeCity(CityNode parentCity, CityNode childCity) {
        childCity.parent = parentCity.val;
        parentCity.children.add(childCity);
        for (CityNode city : childCity.children) {
            city.parent = parentCity.val;
            parentCity.children.add(city);
        }
        childCity.children.clear();
    }
 
    private static void sortPos(int[] xPos, int[] yPos, int n) {
        int i, j, temp;
        // 调整前小后大
        for (i=0; i<n; i++) {
            if (xPos[i] > yPos[i]) {
                temp = xPos[i];
                xPos[i] = yPos[i];
                yPos[i] = temp;
            }
        }
        // 调整整体顺序
        for (i=0; i<n; i++) {
            for (j=0; j<n-i-1; j++) {
                if ((xPos[i] > xPos[i+1]) || (xPos[i] == xPos[i+1] && yPos[i] > yPos[i+1])) {
                    temp = xPos[i];
                    xPos[i] = xPos[i+1];
                    xPos[i+1] = temp;
                    temp = yPos[i];
                    yPos[i] = yPos[i+1];
                    yPos[i+1] = temp;
                }
            }
        }
    }
 
 
}
 
class CityNode {
    int val;
    int parent;
    List<CityNode> children = new ArrayList<>();
 
    public CityNode(int val) {
        this.val = val;
        this.parent = val;
    }
}