跳到主要内容

LeetCode 547. 省份数量

本节目标

用并查集将相连城市合并，统计剩余连通分量。

这是连通性、并查集与二分图中“合并后统计集合数”的母题。城市之间可直接或间接连通；每一个最终 parent 树根代表一个省份。

查看 LeetCode 原题

题意与约束​

isConnected[i][j] = 1 表示城市 i 与 j 直接相连，矩阵是对称的，主对角线为 1。一个城市没有与其他城市相连时，仍独自构成一个省份。两组城市互不相连时，不能只从第一组搜索后就结束。

直接思路与瓶颈​

若对每座城市都沿矩阵重新扩张，或对每一对城市重新判断能否经中间城市抵达，同一个连通块会被重复遍历；在稠密矩阵中，重复可达到 O(n³)。本题只需要最终分量数，不需要恢复路径，适合把“连通”压缩成集合代表元。

图模型与算法推导​

初始有 n 个单元素集合，因此省份数为 n。只扫描矩阵上三角 i < j：每条真实道路若连接两个不同根，unite 成功，两个集合合成一个，省份数减一；若它们已经同根，重复关系不应再次减少计数。最后的计数就是连通块个数。

find 把节点追到代表元并压缩路径，unite 按集合大小把小树挂到大树。它们确保“是否同省”由根而非某个中间父节点决定。

正确性依据​

开始时每城一个集合，计数为省份数。扫描每条上三角连接时，若两根不同，恰好把两个原本不同的连通块合并，省份数减一；若根相同，该边只在已有连通块内部，计数不变。矩阵所有无向边均被检查一次，最终 DSU 集合与图连通分量一一对应，故计数正确。

样例执行过程​

以 [[1,1,0],[1,1,0],[0,0,1]] 为例，初始 parent = [0,1,2]、size = [1,1,1]、provinces = 3。扫描上三角的 (0,1)，两根不同，按大小将 1 挂到 0：parent = [0,0,2]、size = [2,1,1]、provinces = 2。(0,2) 和 (1,2) 均为 0，不合并；扫描结束时两个根是 0、2，返回 2。

代码实现​

C++17
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

class DisjointSet {
    vector<int> parent;
    vector<int> size;

public:
    explicit DisjointSet(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int node) {
        if (parent[node] != node) parent[node] = find(parent[node]);
        return parent[node];
    }

    bool unite(int first, int second) {
        int rootFirst = find(first);
        int rootSecond = find(second);
        if (rootFirst == rootSecond) return false;
        if (size[rootFirst] < size[rootSecond]) swap(rootFirst, rootSecond);
        parent[rootSecond] = rootFirst;
        size[rootFirst] += size[rootSecond];
        return true;
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = static_cast<int>(isConnected.size());
        DisjointSet sets(n);
        int provinces = n;
        for (int city = 0; city < n; city++) {
            for (int other = city + 1; other < n; other++) {
                if (isConnected[city][other] == 1 && sets.unite(city, other)) {
                    provinces--;
                }
            }
        }
        return provinces;
    }
};

实现把 parent 初始化为自身，size 初始化为 1，并同时使用路径压缩与按大小合并。行为测试覆盖一个双城省份加孤立城，以及三个互不相连的城市。

复杂度分析​

矩阵上三角有 O(n²) 个位置，每次 DSU 操作均摊 O(α(n))，总时间 O(n² α(n))，通常写作近似 O(n²)；parent 与 size 的空间为 O(n)。

边界与易错点​

  • 主对角线不是一条需要合并的城市边，扫描 i < j 即可。
  • 扫描整个矩阵也能得到答案，但会重复处理对称边。
  • 只有 unite 返回真时才减少省份数。
  • find 应返回根；直接比较 parent[a] 和 parent[b] 会漏掉间接连接。

模式迁移​

若输入改为道路列表而非矩阵，逐条 unite 即可。若还要查询具体路线，DSU 只知道“是否同组”，应改用 BFS 或 DFS 保存前驱。