LeetCode LCR 116. 省份数量

约 6 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
深度优先搜索 广度优先搜索 LCR 图 并查集

题目描述

✅ LCR 116. 省份数量

image-20260929004703364

image-20260929004703365

题意分析

isConnected[i][j] = 1 表示两座城市直接相连。一个省份包含所有直接或间接连通的城市，因此答案是无向图的连通分量数，而不是直达道路的数量。矩阵对称，对角线表示城市自身。

解法：并查集统计连通块

核心思路

[!blue]

用并查集维护当前已知连通的城市集合。初始每座城市独立成组，parent[i] = i，省份计数 count = n；find(i) 返回所在集合的根，用这个根作为整组的代表。

扫描到直接连接 (i, j) 时，若两城根相同，它们已经通过已处理道路连通，新增这条道路不改变省份数；若根不同，就将两个集合合并，两个连通分量变成一个，count 恰好减一。间接连通会通过一连串合并自动传递，不需要另行枚举路径。

处理完任意一批道路后，并查集中的集合就是这些道路形成的连通分量，count 始终等于集合数。扫描完全部城市对后，它也就是完整图的省份数。矩阵对称，所以只检查 j > i 的上三角，既不重复道路，也跳过自身连接。

find 在回溯时把沿途节点直接挂到根上，压缩后续查找路径。union 按秩把较小秩的根挂到较大秩的根下，只有两根秩相等时才将保留根的秩加一。路径压缩后，秩是用于合并的历史高度上界，不必重新计算真实树高。

解题步骤

  1. 初始化父节点、秩和省份数 count = n。
  2. 枚举上三角城市对 (i, j)，只处理矩阵值为 1 的位置。
  3. 找到两城的根；同根则无需操作，不同根则按秩合并并返回成功。
  4. 仅在成功合并时令 count 减一。
  5. 所有城市对检查完后返回 count。

代码实现

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(\alpha(n))$。
  • 空间复杂度：$O(n)$，保存父节点和秩；查找使用的递归栈不超过此量级。

关键点总结

[!green]

  • 每次成功合并恰好减少一个省份，已经连通的端点不能再次扣减。
  • 同一集合由最终根节点代表，中间父节点不同不代表属于不同省份。
  • 对称矩阵只需扫描上三角，初始单点集合也会计入孤立城市。
  • 路径压缩改变树形，不改变集合归属；按秩合并帮助限制查找路径长度。

易错点总结

[!yellow]

  • 只在两个不同集合成功合并时减少省份数，冗余连接不能重复扣减。
  • 间接连通也属同一省份，判断依据是最终集合根。
  • 按秩合并与路径压缩配合使用；不能仅按 parent 数组里不同中间父节点的数量计数。

相似题目

题目 难度 关联与区别
323. 无向图中连通分量的数目 中等 同样数无向图连通分量，原题边列表输入，本题使用邻接矩阵。
684. 冗余连接 中等 同样用并查集维护连通性，原题遇到已连通端点的新增边时识别冗余，本题最终统计根数量。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/75193690
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！