LeetCode 547.省份数量 题解

题目信息

LeetoCode地址:. - 力扣（LeetCode）

题目理解

如果城市A和城市B相连，城市B和城市C相连，那么城市A,B,C都互相可达，且组成一个省份。清晰直观，我们就不通过引用另外的模型理解了。

同时，题目的输入是一个数组，数组长度是城市个数，每个元素都是一个数组，代表了这个城市和其他哪些城市相连。

例如：isConnected = [[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]

有四个城市编号分别是0,1,2,3

• 0与0,3相连(自己当然和自己是相连的)
• 1与1,2相连
• 2与1,2,3相连
• 3与0,2,3相连

转化成图示化后如下:

很显然，这就是4个集合，如果我们将每个集合的元素按照从小到大排序，也就是isConnected的每一个元素list里的城市编号顺序进行重绘，就会得到：

根据题意，如果两个城市集合中有相同元素，就因为合并这两个集合，因为它们属于一个省份

这与另外一篇题解里的题目类似LeetCode 721.账户合并 题解-CSDN博客，这里就不重复赘述了。

解题思路

数组并查集

上述已经阐明思路，这里直接提供代码

在城市数为n的情况下:

时间复杂度: O(n^3)，构建并查集的时候最耗时，两层循环加find()递归操作。

额外空间复杂度:O(n),用于存储不重复的城市编号和并查集的parent数组。

public int findCircleNum(int[][] isConnected) {
        int cityNum = isConnected.length;
 
        UninFind uninFind = new UninFind(isConnected.length);
        for (int i = 0; i<cityNum; i++) {
            int root = 0;
            //找到第一个相连的城市编号
            while (isConnected[i][root] != 1) {
                root++;
            }
            int child = root+1;
            //遍历之后的相连城市编号，并合并
             for (; child < cityNum; child++) {
                if (isConnected[i][child] == 1) {
                    uninFind.union(child, root);
                }
             }
        }
        Set<Integer> rootSet = new HashSet<>();
        //找到所有城市的集合的不重复的根
        for (int i = 0; i< cityNum; i++) {
            rootSet.add(uninFind.find(i));
        }
        return rootSet.size();
    }
 
    class UninFind {
        int[] parent;
 
        public UninFind(int n) {
            parent = new int[n];
            IntStream.range(0, n).forEach(i -> parent[i] = i);
        }
        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return find(parent[i]);
        }
 
        public void union(int i, int j) {
            parent[find(i)] = find(j);
        }
    }

DFS

如果我们能从isConnected的第一个子数组开始遍历，每遍历到一个城市的编号，就再深入一层去遍历该编号对应于isConnected中的那个子数组，递归的操作，并记录下所有已经遇到的城市编号，递归的终止条件就是已经该城市已经遇到且处理过了。这样处理完第一个子数组之后，我们就已经记录下所有与之相连的城市。此时再遍历第二个子数组，如果该子数组在isConnected的索引编号所代表的城市已经被记录下，那说明已经遍历过了，我们可以直接跳到第三个子数组，否则则重复第一个子数组的的过程，并将最终结果+1.

代码示例如下，在城市数量为n的情况下：

时间复杂度：O(n^2), 最复杂的操作是递归找城市的过程，深度为城市的个数n,每次递归要循环的子数组大小为城市个数n,相乘得到n^2.

额外空间复杂度：O(n),我们需要储存已经访问的城市列表，大小为n.

public int findCircleNum(int[][] isConnected) {
        int num = isConnected.length;
        boolean[] visited = new boolean[num];
        int answer = 0;
        for (int i = 0; i< num; i++) {
            if (!visited[i]) {
                answer++;
                dfs(i, isConnected, visited);
            }
        }
        return answer;
    }
 
    /**
     * 递归的寻找所有还没访问过且与i相连的城市
     * @param i 城市编号
     * @param isConnected
     * @param visited 已经访问过的城市列表
     */
    private void dfs(int i, int[][] isConnected, boolean[] visited) {
        if (visited[i]) {
            return;
        }
        visited[i] = true;
        for (int city = 0; city < isConnected.length; city++) {
            if (i != city && isConnected[i][city] == 1) {
                dfs(city, isConnected, visited);
            }
        }
    }