【华为OD机试 java】城市聚集度

题目

题目说明

【城市聚集度】

一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。

当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，设该城市i的聚集度为DPi（Degree of Polymerization），DPi = max（城市群1的城市个数，城市群2的城市个数，…城市群m 的城市个数）。

请找出地图上DP值最小的城市（即找到城市j，使得DPj = min(DP1,DP2 … DPn))

提示：如果有多个城市都满足条件，这些城市都要找出来（可能存在多个解）

提示：DPi的计算，可以理解为已知一棵树，删除某个节点后；生成的多个子树，求解多个子数节点数的问题。

输入描述：

每个样例：第一行有一个整数N，表示有N个节点。1 <= N <= 1000。

接下来的N-1行每行有两个整数x，y，表示城市x与城市y连接。1 <= x, y <= N

输出描述：

输出城市的编号。如果有多个，按照编号升序输出。

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

5

1 2

2 3

3 4

4 5

输出

3

求解思路

将城市之间的关系抽象为一个无向图，利用BFS搜索连通分量的思路进行求解。在搜索过程中，利用visted记录，没每个节点是否访问过，从而无需对原始数据进行任何更改

代码

package huaweicode;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class CityConcentration {
    private int n;

    private List<int[]> edges;

    private Map<Integer, List<Integer>> edgeMap;

    private boolean[] visited;

    public CityConcentration(String fileName) {
        File  file = new File(fileName);
        try(Scanner scanner = new Scanner(file)){
            System.out.printf("\n读取文件%s\n", fileName);
            n = scanner.nextInt();
            edges = new ArrayList<>();
            while (scanner.hasNext()){
                int[] edge = new int[2];
                edge[0] = scanner.nextInt();
                edge[1] = scanner.nextInt();
                edges.add(edge);
            }
            System.out.printf("共有%d个节点，%d条无向边\n", n, edges.size());
            construct();
        } catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        }
    }

    private void construct(){
        visited = new boolean[n+1];
        edgeMap = new HashMap<>();
        for(int[] edge: edges){
            edgeMap.computeIfAbsent(edge[0], k->new ArrayList<>()).add(edge[1]);
            edgeMap.computeIfAbsent(edge[1], k->new ArrayList<>()).add(edge[0]);
        }
    }

    public void calculate(){
        int min = n+1;
        List<Integer> result = new ArrayList<>();
        for(int i=1; i<=n; i++){
            int dp = calculateMaxDP(i);
            if(dp < min){
                min=dp;
                result.clear();
                result.add(i);
            }else if(dp==min) {
                result.add(i);
            }
        }
        System.out.printf("城市最小聚集度为: %d\n相应的城市序号为: %s", min, result);
    }

    // 记录一个城市的聚集度
    public int calculateMaxDP(int city){
        for(int i=1; i<=n; i++){
            visited[i] = false;
        }
        visited[city] = true;
        int max = -1;

        for(int origin : edgeMap.get(city)){
            visited[origin] = true;
            max = Math.max(max, bfs(origin));
        }
        System.out.printf("城市%d的聚集度为%d\n", city, max);
        return max;
    }


    // bfs搜索，记录一个连通分量的分支
    public int bfs(int origin){
        int len = 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(origin);
        while(!queue.isEmpty()){
            int node = queue.remove();
            for(int next: edgeMap.get(node)){
                if(!visited[next]){
                    queue.add(next);
                    visited[next] = true;
                    len ++;
                }
            }
        }
        return len;
    }

    public static void main(String[] args) {
        String fileName = "E:/leetcode/data/cityConnection%d.txt";
        for(int i=1; i<=3; i++){
            CityConcentration concentration = new CityConcentration(String.format(fileName, i));
            concentration.calculate();
        }
    }
}
           

数据和结果

1. cityConnection1.txt

5
1 2
2 3
3 4
4 5
           

1. cityConnection2.txt

5
1 2
1 3
1 4
1 5
           

1. cityConnection3.txt

8
1 2
2 3
2 4
2 5
5 6
6 7
7 8
           

1. 结果

读取文件E:/leetcode/data/cityConnection1.txt
城市最小聚集度为: 2
相应的城市序号为: [3]
读取文件E:/leetcode/data/cityConnection2.txt
城市最小聚集度为: 1
相应的城市序号为: [1]
读取文件E:/leetcode/data/cityConnection3.txt
城市最小聚集度为: 4
相应的城市序号为: [2, 5]