LeetCode LCR 116. 省份数量

2026-03-28 HGNULB 约 11 分钟

文章信息 5 个分类 · 5 个标签

分类

LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）

标签

深度优先搜索 广度优先搜索 LCR 图 并查集

目录 收起 展开

题目描述

✅ LCR 116. 省份数量

题意分析

输入是一个 n × n 的矩阵 isConnected，isConnected[i][j] == 1 表示第 i 座城市和第 j 座城市之间有直达通路。题目定义「省份」是一组彼此直接或间接相连的城市，要求返回省份的总数。

关键在于「间接」两个字：如果城市 0 与 1 相连、城市 1 与 2 相连，即使 0 和 2 之间没有直达通路，三者也属于同一个省份。所以这不是数矩阵里有多少个 1，而是把城市按「能不能互相到达」这种等价关系分组，然后数分组的个数。

输入形式也给了明确信号：矩阵是对称的（isConnected[i][j] == isConnected[j][i]），对角线恒为 1（每座城市与自己相连）。对称意味着只需要扫描上三角就能覆盖所有城市对，扫描下三角只是把每对重复处理一遍；对角线恒为 1 则是无意义的自环，处理与否都不影响答案，但会影响某些写法的计数。

数据范围是 $1 \le n \le 200$，矩阵最多四万个元素，所以读一遍矩阵的 $O(n^2)$ 开销是躲不掉的下界。

边界情况包括：只有一座城市时答案是 1；矩阵除对角线外全为 0 时答案是 n；矩阵全为 1 时答案是 1。

解法：并查集合并城市

核心思路

一个朴素的想法是给每座城市一个组号，初始各不相同，然后反复扫描矩阵，每遇到一条边就把两端的组号统一成较小的那个，直到某一轮扫描下来所有组号都没有变化为止。这样做是对的，但组号的传播速度太慢：链状的数据下每轮只能往前推进一格，最坏需要 $O(n)$ 轮，每轮又是 $O(n^2)$ 的扫描，总时间劣化到 $O(n^3)$。瓶颈在于「合并信息的传播」被摊到了整张矩阵上。

观察这个瓶颈：我们真正需要的只是「两座城市是否已经同组」这个查询，以及「把两组并成一组」这个操作，完全不需要每次都把整组的组号刷一遍。把每一组组织成一棵树、只用根节点充当这一组的代表，那么查询就是各自往上找根、比较是否相同，合并就是把一棵树的根挂到另一棵树的根下面——只改一个指针。这就是并查集。

整个算法维持一个显式不变量：并查集中的每一棵树恰好对应一个「当前已知彼此连通的城市集合」，且计数器 count 恒等于当前树的棵数。 初始时每座城市自成一棵单点树，count = n，不变量显然成立。每读到一条边 (i, j)：如果 find(i) == find(j)，说明它们已经在同一棵树里，这条边是冗余的，什么都不做，不变量不变；否则两棵不同的树被合并成一棵，树的总数正好减一，于是 count--，不变量继续成立。

扫描完所有边之后，「已知连通」就等于「真正连通」，count 就是省份数量。为了让 find 保持高效，实现上叠加两个标准优化：路径压缩让 find 在回溯时把沿途节点直接挂到根上，按秩合并让矮树挂到高树下面避免树被拉长，两者叠加后单次操作的摊还代价是反阿克曼函数 $\alpha(n)$，在任何现实规模下都不超过 4，可视为常数。

解题步骤

• 初始化 parent[i] = i、rank[i] = 0，并令 count = n。为什么 count 从 n 起步：初始时每座城市都是一个独立的省份，后面只做减法。
• 双重循环枚举城市对，外层 i 从 0 到 n - 1，内层 j 从 i + 1 开始。为什么内层跳过 j <= i：矩阵对称，(i, j) 与 (j, i) 是同一条边；同时这样自然跳过了对角线的自环。
• 当 isConnected[i][j] == 1 时调用 union(i, j)，并且只在它返回 true 时执行 count--。为什么要看返回值：一条边连接的两座城市可能早已通过别的路径连通，这种冗余边不会减少省份数量。
• find 沿 parent 向上递归到根，并在回溯时把 parent[node] 直接改写成根。为什么要回写：不回写只是查到了根，下次还得重走一遍；回写之后这条路径上的所有节点都变成根的直接孩子，树被压扁。
• union 先各自 find 到根，根相同则返回 false；根不同则按秩把矮树的根挂到高树的根下，两棵树等高时任选一棵挂过去并把留下的那个根的秩加一，然后返回 true。为什么必须挂根而不是挂原节点：挂原节点会把该节点原本带着的整棵子树从树上甩掉，破坏集合的完整性。
• 返回 count。

以 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 走一遍：初始 parent = [0, 1, 2]、rank = [0, 0, 0]、count = 3。

i = 0, j = 1：isConnected[0][1] == 1，调用 union(0, 1)。find(0) = 0、find(1) = 1，两根不同；rank[0] 与 rank[1] 都是 0，走等高分支，令 parent[1] = 0 并把 rank[0] 加到 1，返回 true。count 减到 2，此时并查集里有两棵树：{0, 1} 和 {2}，与不变量一致。

i = 0, j = 2：isConnected[0][2] == 0，跳过。

i = 1, j = 2：isConnected[1][2] == 0，跳过。

循环结束，返回 count = 2。检查一下：城市 0 和 1 互连成一个省，城市 2 独自成省，确实是 2 个省份。

代码实现

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind unionFind = new UnionFind(n);
        int count = n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1 && unionFind.union(i, j)) {
                    count--;
                }
            }
        }
        return count;
    }

    private static class UnionFind {
        private final int[] parent;
        private final int[] rank;

        UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int idx = 0; idx < size; idx++) {
                parent[idx] = idx;
            }
        }

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

        boolean union(int first, int second) {
            int rootFirst = find(first);
            int rootSecond = find(second);
            if (rootFirst == rootSecond) {
                return false;
            }

            // 按秩合并让树尽量矮，find 时再做路径压缩。
            if (rank[rootFirst] < rank[rootSecond]) {
                parent[rootFirst] = rootSecond;
            } else if (rank[rootFirst] > rank[rootSecond]) {
                parent[rootSecond] = rootFirst;
            } else {
                parent[rootSecond] = rootFirst;
                rank[rootFirst]++;
            }
            return true;
        }
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    parent := make([]int, n)
    rank := make([]int, n)
    for idx := 0; idx < n; idx++ {
        parent[idx] = idx
    }

    count := n
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if isConnected[i][j] == 1 && unionProvince(parent, rank, i, j) {
                count--
            }
        }
    }
    return count
}

func unionProvince(parent []int, rank []int, first int, second int) bool {
    rootFirst := findProvince(parent, first)
    rootSecond := findProvince(parent, second)
    if rootFirst == rootSecond {
        return false
    }

    // 按秩合并让树尽量矮，find 时再做路径压缩。
    if rank[rootFirst] < rank[rootSecond] {
        parent[rootFirst] = rootSecond
    } else if rank[rootFirst] > rank[rootSecond] {
        parent[rootSecond] = rootFirst
    } else {
        parent[rootSecond] = rootFirst
        rank[rootFirst]++
    }
    return true
}

func findProvince(parent []int, node int) int {
    if parent[node] != node {
        parent[node] = findProvince(parent, parent[node])
    }
    return parent[node]
}

复杂度分析

• 时间复杂度：$O(n^2 \alpha(n))$。读一遍邻接矩阵的上三角就是 $O(n^2)$，这是输入规模决定的下界；矩阵里最多有 $O(n^2)$ 条边，每条边触发一次 union，在路径压缩加按秩合并之下单次操作的摊还代价是反阿克曼函数 $\alpha(n)$，$n \le 200$ 时不超过 4，可视为常数，因此整体近似 $O(n^2)$。
• 空间复杂度：$O(n)$。parent 和 rank 两个数组各占 $n$ 个整数；find 的递归深度受按秩合并约束在 $O(\log n)$ 以内，不改变量级。

关键点总结

• 「省份」就是无向图的连通分量，认出这层等价关系是解题的第一步，之后并查集、DFS、BFS 三条路都能走通。
• count 从 n 开始只减不增，而且只在 union 真正发生合并时才减，冗余边必须被返回值挡掉，否则计数会偏小。
• 路径压缩必须把 find 的结果回写到 parent[node]，只递归查询不回写就失去了压缩的意义。
• 按秩合并的作用是控制树高，秩相等时别忘了给留下的根加一，否则秩恒为 0，优化形同虚设。
• 面试视角：面试官常会先问「不用并查集怎么做」，标准答案是对每个未访问的城市起一次 DFS 或 BFS，把整个连通块标记掉，起了几次就是几个省份，时间同样是 $O(n^2)$ 且空间也是 $O(n)$，代码更短。接着往往会追问「什么时候必须用并查集」，要点是：DFS 适合图结构给定后一次性统计，并查集适合边动态到来、需要随时回答「现在有几个连通块」的场景，例如 305 岛屿数量 II 那类在线加点的题。
• 另一个高频追问是复杂度里的 $\alpha(n)$ 到底是什么，答「反阿克曼函数，增长极慢，现实规模内不超过 4」即可，不必展开证明，但要说清它是摊还代价而非单次最坏代价。

易错点总结

• 错误写法：只要 isConnected[i][j] == 1 就无条件 count--，不检查 union 的返回值。用例 [[1, 1, 1], [1, 1, 1], [1, 1, 1]] → 上三角有 (0,1)、(0,2)、(1,2) 三对，count 从 3 连减三次得到 0，而正确答案是 1，因为其中 (1,2) 是冗余边。
• 错误写法：认为只有直接相连的城市才算同省。用例 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] → 城市 0 与 2 之间没有直达通路就被算成两个省，答案错成 2，正确答案是 1，因为它们通过城市 1 间接连通。
• 错误写法：union 里不先 find 到根，直接写 parent[first] = parent[second]。用例 [[1, 1, 1], [1, 1, 1], [1, 1, 1]] → 处理 (0,1) 后 parent = [1, 1, 2]，处理 (0,2) 后 parent = [2, 1, 2]，此时 1 和 2 分属两棵树，处理 (1,2) 时又被判为一次有效合并，count 一路减到 0，正确答案是 1。
• 错误写法：find 只查不回写，写成 return find(parent[node]) 而不做 parent[node] = find(parent[node])。链状合并出来的树不会被压扁，单次 find 退化成 $O(n)$，整体时间升到 $O(n^3)$；n = 200 时虽然还能过，但这是面试官一眼就会指出的问题。
• 错误写法：按秩合并时把父子关系挂反，rank[rootFirst] < rank[rootSecond] 的分支里写成 parent[rootSecond] = rootFirst。矮树反而成了新根，树高持续增长，答案仍然正确但性能退化到与不做按秩合并一样。
• 错误写法：秩相等的分支里忘记 rank[rootFirst]++。所有节点的秩永远是 0，三个分支永远走同一条，按秩合并彻底失效，退化成随意挂链。
• 错误写法：最后用「parent 数组里有多少个不同的值」当答案，而不是对每个点先 find 再统计。用例 n = 4、依次合并 (0,1)、(2,3)、(1,2) → 最终 parent = [0, 0, 0, 2]，不同的值是 {0, 2} 共两个，答案错成 2，正确答案是 1；节点 3 的父指针停在中间节点 2 上，必须 find(3) 才能拿到真正的根 0。
• 错误写法：count 初值写成 0 再往上加。用例 [[1]] → 没有任何有效合并，直接返回 0，正确答案是 1。
• 错误写法：内层循环从 j = 0 开始。每条边会被处理两次，第二次因为根相同而返回 false，答案本身不会错，但比较次数翻倍；一旦同时犯了第一条「不看返回值就减一」的错误，重复计数会让答案直接跌成负数。

相似题目

题目	难度	考察点
323. 无向图中连通分量的数目	中等	边表输入下的连通分量计数
684. 冗余连接	中等	用合并失败定位成环的多余边
721. 账户合并	中等	字符串映射到下标后再合并
765. 情侣牵手	困难	交换次数等于点数减连通块数
839. 相似字符串组	困难	两两判定相似后再建边合并
990. 等式方程的可满足性	中等	先并等式再用不等式查矛盾
1202. 交换字符串中的元素	中等	连通分量内部自由排序
LCR 117. 相似字符串组	困难	839 题的同题异名版本
LCR 118. 冗余连接	中等	684 题的同题异名版本
面试题 17.07. 婴儿名字	中等	按字典序指定集合的代表元