Leetcode-547-省份数量

题目描述

• 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

• 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

• 给你一个 n x n 的矩阵isConnected，其中isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而isConnected[i][j] = 0表示二者不直接相连。

• 返回矩阵中 省份 的数量。

示例一 ：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

前言

• 可以把 n个城市和它们之间的相连关系看成图，城市是图中的节点，相连关系是图中的边，

• 给定的矩阵 isConnected 即为图的邻接矩阵，

• 省份即为图中的连通分量。

计算省份总数，等价于计算图中的连通分量数，可以通过深度优先搜索或广度优先搜索实现，也可以通过并查集实现。

方法一 ： DFS

• 深度优先搜索的思路很直观
  • 遍历所有的城市，对于每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索
  • 通过矩阵isConnected 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个连通分量
  • 然后对这些城市继续进行深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份
  • 遍历完全部城市以后，即可得到连通分量的总数，即省份的总数。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // 1.初始需要的变量
        int provinces = isConnected.length;                 // 城市数量
        boolean[] visited = new boolean[provinces];         // 标记该城市是否被访问过
        int circles = 0;                                    // 连通分量的数量

        // 2. 遍历所有的城市
        for(int i = 0;i < provinces;i++){
            // 2.1 对于该城市尚未被访问过，从该城市开始深度优先搜索
            if(!visited[i]){                                // 该城市没有被访问过
                dfs(isConnected,visited,provinces,i);       // 2.2 dfs 逻辑
                circles++;                                  // 直到同一个连通分量的所有城市都被访问到，即可得到一个省份
            }
        }
        return circles;
    }
    
    // 2.2 dfs 逻辑
    public void dfs(int[][] isConnected,boolean[] visited,int provinces,int i){
        for(int j = 0;j < provinces;j++){                  // i : 作为起点 ，遍历 i 行元素，得到这一行元素（城市） 哪些是连通的
            if(isConnected[i][j] == 1 && !visited[j]){     // 如果到达一个没有访问过且可达的元素（城市）
                visited[j] = true;                         // 标记为访问过           
                dfs(isConnected,visited,provinces,j);      // j : 作为起点， 遍历 j 行元素，得到这一行元素（城市） 哪些是连通的
            }
        }
    }
}

复杂度分析

• 时间复杂度 ： O(n^2)，其中 n 是城市的数量。需要遍历矩阵 n 中的每个元素。
• 空间复杂度： O(n)，其中 n 是城市的数量。
  • 需要使用数组visited 记录每个城市是否被访问过，数组长度是 n，
  • 递归调用栈的深度不会超过 n。

方法二 ： BFS

• 对于每个城市，如果该城市尚未被访问过，则从该城市开始广度优先搜索，直到同一个连通分量中的所有城市都被访问到，即可得到一个省份。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // 1.初始需要的变量
        int provinces = isConnected.length;                         // 城市数量
        boolean[] visited = new boolean[provinces];                 // 标记该城市是否被访问过
        int circles = 0;                                            // 连通分量的数量

        // 2. BFS 逻辑
        Queue<Integer> queue = new LinkedList<>();                  // 2.1 队列
        for(int i = 0;i < provinces;i++){                           // 遍历每个城市
            if(!visited[i]){                                        // 如果该城市未被访问过
                queue.offer(i);                                     // 从该城市开始BFS搜索
                while(!queue.isEmpty()){                            // 2.2 BFS逻辑
                    int j = queue.poll();                           // 弹出该城市
                    visited[j] = true;                              // 标记该城市为访问过
                    for(int k = 0;k < provinces;k++){               // 遍历与该城市所有邻接的城市
                        if(isConnected[j][k] == 1 && !visited[k]){  // 如果可以访问到
                            queue.offer(k);
                        }
                    }
                }
                circles++;                                          // 直到同一个连通分量中的所有城市都被访问到，即可得到一个省份。
            }
        }
        return circles;
    }
}

复杂度分析

• 时间复杂度 ： O(n^2)，其中 n 是城市的数量。需要遍历isConnected中的每个元素
• 空间复杂度： O(n)，其中 n 是城市的数量。
  • visited 数组长度不会超过n
  • 广度优先搜索队列元素不会超过n

方法三 ： 并查集

• 待学习

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        int[] parent = new int[provinces];
        for (int i = 0; i < provinces; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < provinces; i++) {
            for (int j = i + 1; j < provinces; j++) {
                if (isConnected[i][j] == 1) {
                    union(parent, i, j);
                }
            }
        }
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (parent[i] == i) {
                circles++;
            }
        }
        return circles;
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
}

打赏