1. 题目描述

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

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

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

示例 1：
graph1.jpg

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

示例 2：
547. 省份数量 - 图2

  1. 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
  2. 输出：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）深度优先遍历

    1. /**
    2. * @param {number[][]} isConnected
    3. * @return {number}
    4. */
    5. var findCircleNum = function(isConnected) {
    6.   let res = 0, i = -1, visited = new Uint8Array(isConnected.length)
    7.   const dfs = i => {
    8.       visited[i] = 1
    9.       for(let j = isConnected[i].length; j >=0; j--){
    10.           if(isConnected[i][j] && visited[j] === 0){
    11.               dfs(j)
    12.           }
    13.       }
    14.   }
    15.   while(++i < isConnected.length){
    16.       if(visited[i] === 0){
    17.           res++
    18.           dfs(i)
    19.       }
    20.   }
    21.   return res
    22. };

    （2）广度优先遍历

    1. /**
    2. * @param {number[][]} isConnected
    3. * @return {number}
    4. */
    5. var findCircleNum = function(isConnected) {
    6.   let res = 0, i = -1, visited = new Uint8Array(isConnected.length), queue = []
    8.   while(++i < isConnected.length){
    9.       if(visited[i] === 0){
    10.           res++
    11.           queue.push(i)
    12.           while(queue.length){
    13.               const val = queue.shift()
    14.               visited[val] = 1
    15.               for(let j = 0; j < isConnected[val].length; j++){
    16.                   if(isConnected[val][j] && visited[j] === 0){
    17.                       queue.push(j)
    18.                   }
    19.               }
    20.           }
    21.       }
    22.   }
    23.   return res
    24. };

    4. 提交结果

    （1）深度优先遍历
    image.png
    （2）广度优先遍历
    image.png