LeetCode 547. 省份数量

2024-09-23 HGNULB 约 7 分钟

文章信息 13 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 10-20 LeetCode 75 腾讯字节华为微软拼多多虾皮猿辅导

题目描述

✅ 547. 省份数量

题意分析

把城市看成顶点，把 isConnected[i][j] == 1 看成无向边。直接或间接相连的城市属于同一个省份，因此答案就是无向图的连通分量个数。

矩阵中的一行只表示某座城市的直连关系，不能直接用它判断整个省份。需要把每条边两端所属的城市组不断合并，让间接连接也归入同一个组。

解法：并查集合并城市

核心思路

[!blue]

使用并查集维护城市所属的组。parent[x] 是节点 x 的父节点，满足 parent[root] == root 的节点是这一组的代表；find(x) 沿父节点找到代表根。同根的城市已经连通，不同根的城市属于两个不同连通块。

开始时每座城市独立成组，令 count = n。遇到一条直连边时，先找到两端的根：若根不同，这条边把两个连通块接成一个，合并两个根并将 count 减一；若根相同，两端早已通过处理过的边连通，这条边不会减少省份数量。代码让 union 返回是否真正合并，调用方据此更新计数。

合并时把秩较小的根接到秩较大的根下，避免树退化成长链；秩相同才让保留的根增加一。find 返回时把沿途节点直接连接到根，称为路径压缩，它只缩短路径，不改变集合归属。压缩以后 rank 不一定等于实际树高，仍可作为合并方向的依据。

每处理一条边，并查集都会准确表示当前这些边产生的连通分量，计数也同步保持正确；全部边处理后，自然就得到整张图的省份数量。题目保证矩阵对称，每条无向边只需处理一次，所以枚举 i < j 的上三角即可；对角线只是城市与自身相连，无需合并。

解题步骤

初始化 parent[i] = i、rank[i] = 0，每座城市各自成组，count = n。

枚举所有 0 <= i < j < n 的城市对，跳过没有直连关系的位置。

对每条直连边分别调用 find，取得两端的根，并在查找过程中压缩路径。

两根相同则返回合并失败；否则按秩连接两个根，返回合并成功，外层执行 count--。

所有城市对处理完后返回 count。孤立城市从未参与成功合并，会保留为一个独立省份。

代码实现

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = 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 && uf.union(i, j)) {
                    // 只有两个不同集合真正合并时，省份数量才减少。
                    count--;
                }
            }
        }

        return count;
    }

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

        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];

            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int find(int x) {
            if (parent[x] != x) {
                // 递归找到代表根后压缩路径，后续查找不必重复走中间链。
                parent[x] = find(parent[x]);
            }

            return parent[x];
        }

        boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) {
                return false;
            }

            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }

            return true;
        }
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    parent := make([]int, n)
    rank := make([]int, n)
    for i := range parent {
        parent[i] = i
    }

    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 findProvince(parent []int, x int) int {
    if parent[x] != x {
        // 递归找到代表根后压缩路径，后续查找不必重复走中间链。
        parent[x] = findProvince(parent, parent[x])
    }
    return parent[x]
}

func unionProvince(parent, rank []int, x, y int) bool {
    rootX := findProvince(parent, x)
    rootY := findProvince(parent, y)
    if rootX == rootY {
        return false
    }

    if rank[rootX] < rank[rootY] {
        parent[rootX] = rootY
    } else if rank[rootX] > rank[rootY] {
        parent[rootY] = rootX
    } else {
        parent[rootY] = rootX
        rank[rootX]++
    }
    return true
}

复杂度分析

时间复杂度：$O(n^2 \alpha(n))$。上三角有 $O(n^2)$ 个位置；路径压缩与按秩合并使每次并查集操作的摊还复杂度为 $O(\alpha(n))$，其中 $\alpha$ 是增长极慢的反阿克曼函数。

空间复杂度：$O(n)$。parent、rank 数组以及递归查找使用的栈空间都包含在此范围内。

关键点总结

[!green]

省份对应连通分量，不能只统计某座城市的直连邻居。

只有两个不同根真正合并，连通分量数量才会减少一。

find 处理间接归属，路径压缩加快查找，按秩合并控制树的增长。

利用矩阵对称性只扫描上三角，不会遗漏任何无向边。

易错点总结

[!yellow]

每遇到一个 1 就减一，会把自环、重复边和已经连通的城市再次计入合并。

只连接原节点而不先找根，可能破坏原有集合关系；需要连接的是两个集合的代表根。

直接统计 parent 数组中不同值的数量不可靠，部分节点仍可能指向中间节点；本实现用成功合并次数维护 count。

秩相同时，合并后只增加保留根的秩；秩不同时无需增加，路径压缩也不需要重算秩。

内层从 i + 1 开始即可，反向边和对角线都不提供新的连通信息。

相似题目

题目	难度	关联与区别
323. 无向图中连通分量的数目	中等	同样数无向图连通分量，原题边列表输入，本题使用邻接矩阵。
684. 冗余连接	中等	同样用并查集维护连通性，原题遇到已连通端点的新增边时识别冗余，本题最终统计根数量。
1319. 连通网络的操作次数	中等	用并查集合并连通分量；本题按邻接矩阵合并城市，该题统计网络连通分量与可用冗余边。
721. 账户合并	中等	用并查集合并连通分量；本题按邻接矩阵合并城市，该题按共享邮箱合并账户。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2024/55155236

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！