LeetCode 323. 无向图中连通分量的数目

2021-08-10 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等未解决会员题 1-2 腾讯

题目描述

✅ 323. 无向图中连通分量的数目

题意分析

图中有 n 个节点，编号为 0 到 n - 1，每条边表示两个端点可以互相到达。一个连通分量由所有彼此可达的节点组成，组外节点与这组均不连通，要求统计这样的组有多少个。没有出现在任何边中的孤立点也各自构成一个分量。

解法：并查集计数连通块

核心思路

[!blue]

可以把边逐条加入图中。没有处理任何边时，所有节点互不相连，共有 n 个分量；每加入一条边，只可能把它两端所在的两个分量连接起来，不会影响其他分量。因此用并查集维护当前分组，同时维护计数 components。

parent 把每个集合组织成一棵以代表节点为根的树，根满足 parent[root] == root。find(node) 沿父指针找到这个根，同根就表示已经连通。不能只比较端点的直接父节点，因为同一集合中的不同节点可能还经过不同的中间父节点。

处理边 (u, v) 时，先得到 rootA、rootB：若相同，这条边只是在已有连通分量内部增加连接，计数不变；若不同，连接两个根，原来的两个分量变成一个，恰好令 components--。所以无论图中有多少环，都只对真正合并的那一次减一。

为了让父指针树尽量浅，size[root] 保存根所在集合的节点数，始终把小集合的根挂到大集合的根下，并增加大集合的大小。查找时还采用路径折半：让当前节点直接指向祖父节点，再沿新父节点继续。祖父和原父属于同一集合，所以根和连通关系不变，但以后查找需要经过的层数更少。

初始化使并查集与无边图的连通分量完全一致；每条边只在两个分量原本不同的情况下合并它们，继续保持这一对应关系。所有边处理完时，components 就是原图的连通分量数。孤立点从未被合并，因此已经包含在答案中。

解题步骤

初始化每个节点为自己的根，集合大小为一，分量数为 n。

逐条边查找两个根。

同根跳过，不同根按大小合并并将数量减一。

返回最终分量数。

代码实现

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] parent = new int[n];
        int[] size = new int[n];

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

        int components = n;

        for (int[] edge : edges) {
            int rootA = find(parent, edge[0]);
            int rootB = find(parent, edge[1]);

            // 同一分量内的边不减少分量数量。
            if (rootA == rootB) {
                continue;
            }

            if (size[rootA] < size[rootB]) {
                int temp = rootA;

                rootA = rootB;
                rootB = temp;
            }

            // 小集合挂到大集合，只有这次成功合并才减少一个分量。
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            components--;
        }

        return components;
    }

    private int find(int[] parent, int node) {
        while (node != parent[node]) {
            parent[node] = parent[parent[node]];
            node = parent[node];
        }

        return node;
    }
}

func countComponents(n int, edges [][]int) int {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }

    find := func(node int) int {
        for node != parent[node] {
            parent[node] = parent[parent[node]]
            node = parent[node]
        }
        return node
    }

    components := n
    for _, edge := range edges {
        rootA := find(edge[0])
        rootB := find(edge[1])
        // 同一分量内的边不减少分量数量。
        if rootA == rootB {
            continue
        }
        if size[rootA] < size[rootB] {
            rootA, rootB = rootB, rootA
        }
        // 小集合挂到大集合，只有这次成功合并才减少一个分量。
        parent[rootB] = rootA
        size[rootA] += size[rootB]
        components--
    }
    return components
}

复杂度分析

时间复杂度：$O(n+Eα(n))$，E 为边数，α 为反阿克曼函数。

空间复杂度：$O(n)$，保存父节点和集合大小。

关键点总结

[!green]

减一对应两个分量真正合并，不对应每条输入边。

必须比较根，直接父节点可能不同但仍属于同一集合。

孤立点从初始化时就计入，无需另行统计。

易错点总结

[!yellow]

每条边都减一：环内的边会造成重复扣减。

默认父数组全部为零：错误地把节点视为同一组。

只统计边中出现的节点：漏掉孤立点。

相似题目

题目	难度	关联与区别
547. 省份数量	中等	连通分量目标相同，原题输入邻接矩阵，本题输入边列表。
200. 岛屿数量	中等	网格相邻关系也能看作无向边，岛屿就是隐式图中的连通分量。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/42037537

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