leetcode：547. 省份数量

题目

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

示例 1：
[中等] 547. 省份数量 - 图1

  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

解答 & 代码

解法一：DFS

思路近似于[中等] 200. 岛屿数量，就是求连通分量的数量

  • 设置一个 visited 数组，visited[i] 代表第 i 个城市是否被访问过

  • 遍历每个城市，如果该城市未被访问过，则从该城市开始深度优先搜索（DFS），将其所在连通分量的所有城市都标记为已访问：

    • 通过邻接矩阵 isConnected，访问所有与当前城市相邻的且未被访问过的城市，标记为已访问，再以这些城市为起点继续 DFS，直到该连通分量全部被标记已访问

      1. class Solution {
      2. private:
      3. // 从 idx 开始深度优先遍历，将其所在连通分量的虽有城市都标记为已访问
      4. void dfs(vector<vector<int>>& isConnected, vector<bool>& visited, int idx)
      5. {
      6.    int cityCnt = visited.size();
      7.    if(idx < 0 || idx >= cityCnt || visited[idx] == true)
      8.        return;
      10.    visited[idx] = true;
      11.    for(int next = 0; next < cityCnt; ++next)
      12.    {
      13.        if(isConnected[idx][next] == 1 && visited[next] == false)
      14.            dfs(isConnected, visited, next);
      15.    }
      16. }
      17. public:
      18. int findCircleNum(vector<vector<int>>& isConnected) {
      19.    int cityCnt = isConnected.size();        // 城市数量（图的节点数量）
      20.    int provinceCnt = 0;                    // 省份数量（连通分量数量）
      21.    vector<bool> visited(cityCnt, false);    // visited[i] 代表第 i 个城市是否已被访问过
      22.    // 遍历每个城市
      23.    for(int i = 0; i < cityCnt; ++i)
      24.    {
      25.        // 若当前城市未被访问过，则从当前城市开始 DFS，将其所在连通分量的所有城市都标记为已访问
      26.        if(visited[i] == false)
      27.        {
      28.            ++provinceCnt;                    // 省份数量（连通分量数量）+1
      29.            dfs(isConnected, visited, i);    
      30.        }
      31.    }
      32.    return provinceCnt;
      33. }
      34. };

      复杂度分析：设有 n 个城市

  • 时间复杂度[中等] 547. 省份数量 - 图3：遍历邻接矩阵 isConnected的每个元素

  • 空间复杂度 O(n)：visited 数组长为 n；递归栈深度不超过 n

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 71.06% 的用户
  4. 内存消耗：13.4 MB, 在所有 C++ 提交中击败了 57.60% 的用户

解法二：并查集

[算法拾级]不相交集(并查集) - 知乎

设城市数量（节点数量）为 n

  1. 建立包含 n 个节点的并查集
  2. 遍历邻接矩阵 isConnected 的上三角（不含对角线），如果 isConnected[i][j] == 1，说明节点 i 和节点 j 相连，则合并两个节点所在的连通分支

省份数量（连通分支数量） = 城市数量（节点数量） - 合并次数

或者统计并查集中根节点数量，即 parents[i] == i 的数量，就是连通分支数量

  1. /* 并查集类 */
  2. class UnionFind {
  3. private:
  4.     vector<int> parents;            // 父节点数组，parent[i] 代表节点 i 的父节点
  5. public:
  6.     /* 构造函数 */
  7.     UnionFind(int n)
  8.     {
  9.         parents.resize(n);
  10.         for(int i = 0; i < n; ++i)    // 将每个节点的父节点都初始化为自己本身
  11.             parents[i] = i;
  12.     }
  14.     /* 递归查询节点 x 的根节点并返回，寻找根节点的过程进行路径压缩 */
  15.     int find(int x)
  16.     {
  17.         // 递归结束条件：如果节点 x 的父节点是 x 本身，说明 x 已经是根节点，直接返回
  18.         if(x == parents[x])
  19.             return x;
  21.         parents[x] = find(parents[x]);    // 递归寻找 x 的根节点
  22.         return parents[x];
  23.     }
  25.     /* 合并操作：x 在一个连通图中，y 在一个连通图中，x 和 y 相连，合并两个连通图 */
  26.     void _union(int x, int y, int& mergeCnt)
  27.     {
  28.         int rootX = find(x);    // x 的根节点
  29.         int rootY = find(y);    // y 的根节点
  30.         if(rootX == rootY)        // 如果节点 x、y 的根节点相同，则无需合并
  31.             return;
  33.         // 合并两个连通图
  34.         ++mergeCnt;                    // 合并次数 + 1
  35.         parents[rootX] = rootY;        // 将 x 的根节点指向 y 的根节点
  36.     }
  37. };
  39. class Solution {
  40. public:
  41.     int findCircleNum(vector<vector<int>>& isConnected) {
  42.         int cityCnt = isConnected.size();        // 城市数量（图中节点数量）
  43.         UnionFind uf(cityCnt);                    // 并查集
  44.         int mergeCnt = 0;                        // 合并次数
  45.         // 遍历邻接矩阵 isConnected 的上三角（不含对角线）
  46.         for(int i = 0; i < cityCnt; ++i)
  47.         {
  48.             for(int j = i + 1; j < cityCnt; ++j)
  49.             {
  50.                 if(isConnected[i][j] == 1)        // 若点 i 和 j 相连，则合并 i 和 j 的连通图 
  51.                     uf._union(i, j, mergeCnt);
  52.             }
  53.         }
  55.         // 省份数量（连通分支数量） = 城市数量（节点数量） - 合并次数
  56.         int provinceCnt = cityCnt - mergeCnt;
  57.         return provinceCnt;
  58.     }
  59. };

复杂度分析：设有 n 个城市

  • 时间复杂度[中等] 547. 省份数量 - 图4：遍历邻接矩阵 isConnected上三角的每个元素，时间复杂度[中等] 547. 省份数量 - 图5；如果该元素为 1，则需要调用 _union 进行合并， _union 中又要调用两次 find 递归查找根节点，时间复杂度为 O(log n)
  • 空间复杂度 O(n)：并查集中 parents 数组长为 n

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 71.06% 的用户
  4. 内存消耗：13.4 MB, 在所有 C++ 提交中击败了 48.65% 的用户