2021-01-07 | 547. 省份数量

た入场券 2023-01-04 14:50 116阅读 0赞

### 1. 题目描述 ###

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

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

给你一个 `n x n` 的矩阵 `isConnected` ，其中 `isConnected[i][j] = 1` 表示第 `i` 个城市和第 `j` 个城市直接相连，而 `isConnected[i][j] = 0` 表示二者不直接相连。  
返回矩阵中 **省份** 的数量。

**示例 1：**  
![在这里插入图片描述][20210110222233727.jpg]

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

**示例 2：**  
![在这里插入图片描述][20210110222241462.jpg]

输入：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]`

### 2. 解题思路 ###

对于这道题，可以想象到这个一个图的结构。对于图，我们常用的两种方式就是**深度优先遍历**和**广度优先遍历**，这里就分别用这两种方法来解答这个问题。

**（1）深度优先遍历**  
深度优先遍历就是遍历所有的城市，对于每个城市，如果该城市未被访问过，则从该城市进行深度优先搜索。通过矩阵`isConnected` 得到该城市相连的城市，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。遍历完全部城市以后，即可得到连通分量的总数，即省份的总数。

这里我们使用res来记录城市数量，每次深度优先遍历到头之后，res就加一。

**复杂度分析**

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

**（2）广度优先遍历**  
先放入的节点应优先被遍历，适合**队列。**  
挂不挂度优先遍历就是对于每个城市，如果该城市尚未被访问过，则从该城市开始广度优先搜索，直到同一个连通分量中的所有城市都被访问到，即可得到一个省份。

**复杂度分析**

*  **时间复杂度**：O(n)，其中 n 是城市的数量。需要遍历矩阵 isConnected 中的每个元素。
 *  **空间复杂度**：O(n)，其中 n 是城市的数量。需要使用数组 visited 记录每个城市是否被访问过，数组长度是 n，广度优先搜索使用的队列的元素个数不会超过 n。

### 3. 代码实现 ###

**（1）深度优先遍历**

/** * @param {number[][]} isConnected * @return {number} */
    var findCircleNum = function(isConnected) { 
        let res = 0, i = -1, visited = new Uint8Array(isConnected.length)
        const dfs = i => { 
            visited[i] = 1
            for(let j = isConnected[i].length; j >=0; j--){ 
                if(isConnected[i][j] && visited[j] === 0){ 
                    dfs(j)
                }
            }
        }
        while(++i < isConnected.length){ 
            if(visited[i] === 0){ 
                res++
                dfs(i)
            }
        }
        return res
    };

**（2）广度优先遍历**

/** * @param {number[][]} isConnected * @return {number} */
    var findCircleNum = function(isConnected) { 
        let res = 0, i = -1, visited = new Uint8Array(isConnected.length), queue = []
    
        while(++i < isConnected.length){ 
            if(visited[i] === 0){ 
                res++
                queue.push(i)
                while(queue.length){ 
                    const val = queue.shift()
                    visited[val] = 1
                    for(let j = 0; j < isConnected[val].length; j++){ 
                        if(isConnected[val][j] && visited[j] === 0){ 
                            queue.push(j)
                        }
                    }
                }
            }
        }
        return res
    };

### 4. 提交结果 ###

**（1）深度优先遍历**  
![在这里插入图片描述][20210110222319406.png]

**（2）广度优先遍历**  
![在这里插入图片描述][20210110222326374.png]

[20210110222233727.jpg]: /images/20221119/e89786e083134ffbbfa17fd7674e840a.png
[20210110222241462.jpg]: /images/20221119/f582ea31e206489ba9298d644cda9373.png
[20210110222319406.png]: /images/20221119/acf5fa86e51b437f86a5a6b6f4378ef7.png?
[20210110222326374.png]: /images/20221119/4ed1f76b5ffc43e0a2c4be27ca71a63a.png?