CC++ & Algorithm

并查集的概念与基本实现

困难3
语言版本：通用
概述：并查集是用来管理“谁和谁是一伙的”的数据结构，能够快速合并两个团体，并查询两个人是否属于同一个团体。

并查集：轻松管理“谁和谁是一伙的”

你有没有遇到过这样的问题：在班级里，同学们分成几个小组做项目，你想知道任意两个同学是不是在同一个小组；或者你在玩一个联机游戏，想知道两个玩家是否属于同一个公会；又或者老师让你统计“朋友的朋友是不是也是朋友”……这些场景听起来很不一样，但背后都藏着同一个问题：怎样快速判断两个元素是否属于同一个集合，并且能够把两个集合合并起来？

计算机科学家们发明了一种非常巧妙的数据结构——并查集（Union-Find），专门用来解决这类问题。它的核心思想超级简单：就像在班级里选“组长”，每个小组都有一个组长，要想知道两个人是不是一组的，只需要看看他们的组长是不是同一个人。如果两个小组决定合并，就让其中一个组长“认”另一个组长为老大，所有人就都属于新的大组了。今天，我们就来把这种“找组长、合并组长”的想法变成代码，并且搞清楚它的每个细节。

从生活中找例子：为什么需要并查集？

案例一：班级分组

想象一下，你所在的班级有40个同学。开学第一天，老师让大家自由分组做项目。一开始，每个同学都是单独一个人，没有和任何人组队。这时，如果有人想知道“小明和小红是不是一个组的？”，我们只能一个个去问他们的组员名单，非常麻烦。

过了几天，有些同学开始互相认识并组成了小组。比如，小明、小刚、小华组成了一个3人小组，他们推选小明作为“组长”。同样，小红、小丽组成了一个2人小组，小红是组长。现在，当我们问“小明和小红是不是一组的？”时，我们可以先看小明有没有组长，再看小红有没有组长，发现他们组长不同，就知道他们不是一组的。

接着，两个小组决定合并。小明组和小红组通过商量，决定全部归到小明名下，小红不再是组长，所有成员都认小明为组长。这样，合并后的团体就只有一个组长了。这种“找组长”、“合并组长”的思想，就是并查集的核心。

我们可以用一张图来表示这个过程。每个同学是一个节点，组长就是根节点。一开始每个节点自己就是根。

初始： 1  2  3  4  5 ... （每个人都是独立的）
        |  |  |  |  |
        v  v  v  v  v
        1  2  3  4  5 ... （自己指向自己）

合并1和2：让2的组长变成1
        1    3    4    5 ...
       /
      2

再合并1组和3组：让3的组长变成1
        1        4    5 ...
       / \
      2   3

现在，如果想查询2和3是不是一组，只要找到2的组长（1），找到3的组长（1），组长相同，所以是一组。

案例二：游戏中的“好友圈”

在一个手机游戏里，有10个玩家。系统可以查询两个玩家是否在同一个“好友圈”中（好友圈的定义是：如果A和B是好友，B和C是好友，那么A、B、C在同一好友圈）。一开始，每个玩家自己就是一个圈。如果玩家1添加了玩家2为好友，就把他们俩的圈合并；接着玩家2添加了玩家3为好友，再把玩家1、2的圈和玩家3的圈合并。最后，如果玩家1和玩家4是好友，继续合并。这样，用并查集就能快速回答：“玩家1和玩家5是不是在同一个好友圈？”只需要找到他们的组长（根节点）比较一下就行。

案例三：家族关系

你正在帮历史老师整理一个家族的族谱。已知一些父子关系，比如“A是B的父亲，B是C的父亲，D是E的父亲”。现在想知道“C和E是不是同一个家族的？” 可以先把这些关系用并查集合起来：把父亲当作组长，儿子指向父亲。然后查找C的组长和E的组长，如果相同就是一家人，否则不是。如果后来发现“E和C其实是同一个祖先”，就把两个家族合并。

数据结构原理：用数组模拟“组长链”

并查集（Union-Find）是一种树形的数据结构，用来处理不相交集合的合并与查询问题。它主要支持两种操作：

  • 查找（Find）：给定一个元素，找到它属于哪个集合（通常返回该集合的代表元素，也就是组长）。
  • 合并（Union）：将两个元素所在的集合合并成一个集合。

在实现中，我们用一个数组 parent 来记录每个元素的父节点。如果 parent[i] == i，说明 i 是自己的组长（根节点）。否则，parent[i] 是 i 的上级。那么查找一个元素属于哪个集合，就是不断找它的父节点，直到找到根节点。

合并两个集合时，只要把一个集合的根节点的父节点指向另一个集合的根节点，就完成了合并。

这种最简单的实现，没有做任何优化。如果树很高，查找就会很慢（比如链状）。后面我们会学习优化方法。

关键概念详解

  1. 根节点（组长）：一个集合中，只有根节点的 parent[x] == x。所有其他节点通过链条最终都指向根节点。
  2. 查找路径：从某个节点出发，沿着 parent 指针一直向上，直到到达根节点。这个过程可能很长，如果树退化成一条链，查找一个节点可能需要遍历所有节点。
  3. 合并方向：合并时，通常把一个根节点的 parent 指向另一个根节点。两个根节点谁指向谁都可以，但不同的选择会影响树的形状。后面我们会学到“按秩合并”来优化。

新手容易犯的错误

错误1：忘记初始化 parent 数组

初始化时，一定要让每个元素的 parent[i] = i。如果忘记初始化，或者初始化为 0 或其他值，会导致查找时找不到根节点，程序可能死循环或得到错误结果。

正确做法：在构造函数中遍历所有元素，让每个元素指向自己。

错误2：合并时直接让某个节点的父节点指向另一个节点，而不是合并根节点

假设有两个集合，根节点分别是 rootX 和 rootY。错误的做法是直接写 parent[x] = y，这样只把 x 自己指向了 y，但 x 原来的根节点仍然存在，整个集合并没有真正合并，后续查找会混乱。

正确做法：先找到两个元素的根节点，然后让其中一个根指向另一个根：parent[rootY] = rootX。

错误3：在 find 函数中没有循环终止条件

查找时，必须一直往上直到 parent[x] == x。如果写成了 while (parent[x] != x) { x = parent[x]; } 是正确的。但有些初学者会写成 while (true) { x = parent[x]; }，没有终止条件，会死循环。

错误4：没有考虑“本身就在同一集合”的情况

在 unite 函数中，如果 rootX == rootY，说明两个元素已经在同一集合，此时不应再做任何操作，否则可能导致循环（比如让根指向自己？）或者浪费性能。应该先判断再合并。

错误5：混淆“查找”和“合并”的方向

在合并时，有人会写 parent[rootX] = rootY 或 parent[rootY] = rootX，两种都行，但必须统一。如果后面用到了按秩合并，就会根据秩大小决定合并方向。

完整代码示例：带注释的C++和Python实现

下面给出一个最基本的并查集代码，用于班级分组问题。注意每一行变量定义都写了中文注释，方便理解。

C++ 版本

#include <iostream>
#include <vector>
using namespace std;

class DSU {
private:
    vector<int> parent;  // parent[i] 表示第i个元素的父节点
public:
    // 构造函数：初始化n个元素，每个元素单独成为一个集合
    DSU(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;   // 每个元素指向自己，代表自己是组长
        }
    }

    // 查找操作：找到元素x所在集合的根节点（组长）
    int find(int x) {
        // 如果x的父节点不是自己，就继续向上找
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;   // 返回根节点
    }

    // 合并操作：将元素x和元素y所在的集合合并
    void unite(int x, int y) {
        int rootX = find(x);  // 找到x的根
        int rootY = find(y);  // 找到y的根
        if (rootX == rootY) return;  // 如果已经在同一个集合，不用合并
        parent[rootY] = rootX;       // 让rootY的父节点变成rootX，合并完成
    }

    // 判断两个元素是否属于同一个集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    // 假设有5个同学，编号0~4
    DSU dsu(5);

    // 合并0和1
    dsu.unite(0, 1);
    // 合并1和2
    dsu.unite(1, 2);
    // 合并3和4
    dsu.unite(3, 4);

    // 查询0和2是否一组
    cout << "0和2是否一组？ " << (dsu.same(0, 2) ? "是" : "否") << endl;  // 输出：是
    // 查询0和3是否一组
    cout << "0和3是否一组？ " << (dsu.same(0, 3) ? "是" : "否") << endl;  // 输出：否

    // 合并0所在组和3所在组
    dsu.unite(0, 3);
    cout << "合并后0和3是否一组？ " << (dsu.same(0, 3) ? "是" : "否") << endl;  // 输出：是

    return 0;
}

Python 版本

class DSU:
    def __init__(self, n):
        # 初始化父节点数组，每个元素指向自己
        self.parent = list(range(n))

    def find(self, x):
        # 查找x的根节点
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        # 合并x和y所在的集合
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        self.parent[root_y] = root_x  # 将y的根指向x的根

    def same(self, x, y):
        # 判断x和y是否在同一集合
        return self.find(x) == self.find(y)


# 测试
if __name__ == "__main__":
    dsu = DSU(5)
    dsu.union(0, 1)
    dsu.union(1, 2)
    dsu.union(3, 4)
    print("0和2是否一组？", dsu.same(0, 2))  # True
    print("0和3是否一组？", dsu.same(0, 3))  # False
    dsu.union(0, 3)
    print("合并后0和3是否一组？", dsu.same(0, 3))  # True

运行结果说明

以上代码输出如下：

0和2是否一组？ 是
0和3是否一组？ 否
合并后0和3是否一组？ 是

这完全符合我们生活中的例子：0、1、2先组成一组，3和4组成另一组，然后合并0组和3组，最后所有人都在同一组。

完整应用示例：判断网络中的计算机是否连通

假设有5台计算机，编号0~4，它们之间通过网线连接。已知以下连接关系：0-1，1-2，3-4。现在想判断0和2是否连通，0和3是否连通，以及如果加上连接0-3后，所有计算机是否都连通了？我们可以直接用并查集解决。

# 使用上面的DSU类
dsu = DSU(5)
# 添加已知连接
for (a, b) in [(0,1), (1,2), (3,4)]:
    dsu.union(a, b)

print("0和2连通吗？", dsu.same(0,2))  # True
print("0和3连通吗？", dsu.same(0,3))  # False

# 添加新连接0-3
dsu.union(0,3)
print("添加0-3后，0和3连通吗？", dsu.same(0,3))  # True
print("所有计算机是否全部连通？", len(set(dsu.find(i) for i in range(5))) == 1)  # True

总结要点

  1. 并查集是什么：一种用来管理多个不相交集合的数据结构，可以快速知道两个元素是否属于同一集合，并且可以快速合并两个集合。
  2. 核心操作：find（查找根节点）和union（合并两个根）。
  3. 数组实现：用parent数组记录每个元素的父节点，根节点满足parent[i]==i。
  4. 时间复杂度：最坏情况下，如果树变成一条链，find需要 O(n) 时间。但实际使用中，通过优化可以达到接近常数时间。
  5. 适用场景：网络连通性、社交网络朋友圈、图的最小生成树（Kruskal算法）、游戏中的阵营判断、家族关系推理等。
  6. 注意事项：基本实现容易退化成链，必须配合路径压缩或按秩合并优化。新手容易犯的错误包括忘记初始化、合并时没找根、没判断已在同一集合等。

并查集就像一个“组织关系管理器”，你只需要告诉它谁和谁是一组的，它就能迅速回答“他们是不是一伙的”，并且能帮你把不同团体合并在一起。是计算机科学中非常实用的工具。

相关知识点指引

学完基本的并查集后，你应该进一步了解以下优化，它们可以让并查集的效率从 O(n) 提升到几乎 O(1)：

  • 路径压缩（Path Compression）：在 find 的过程中，把沿途所有节点直接指向根节点，这样下次查找就一步到位。
  • 按秩合并（Union by Rank）：合并时，总是把高度较小的树连接到高度较大的树下，避免树变高。
  • 带权并查集：除了记录集合关系，还能记录节点之间的相对关系（比如“距离”），常用于处理“敌人”或“朋友”的变种问题。

如果你对图算法感兴趣，并查集是 Kruskal 最小生成树算法的核心工具，也是许多连通性问题的基石。想练习的话，可以在 LeetCode 上搜索“并查集”或“Union Find”，有大量经典题目等着你，比如“朋友圈”、“岛屿数量”、“冗余连接”等。

例题精讲

1单选题

在并查集中，如果同时使用了路径压缩和按秩合并优化，那么单次查找（find）操作的均摊时间复杂度最接近以下哪个？

AO(n)
BO(log n)
CO(α(n))
DO(1)
2单选题

以下关于并查集基本操作的叙述中，错误的是？

A查找（find）操作用于找到元素所在集合的代表元素
B合并（union）操作用于将两个元素所在的集合合并为一个集合
C路径压缩可以在查找的同时将路径上的所有节点直接连接到根节点
D按秩合并可以保证每次查找的时间复杂度严格为 O(log n)
3判断题

并查集可以用于判断无向图中是否存在环（假设图中有 n 个顶点，按顺序加入边，每加入一条边时用并查集检查两个顶点是否已在同一集合中）。

4填空题
以下是用递归实现的带路径压缩的查找函数，请补全空白处。

int find(int x) {
    if (parent[x] != x) {
        parent[x] = ___;
    }
    return parent[x];
}
5填空题
下面是按秩合并的合并函数，请在空白处填上适当内容。

void unionSet(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) {
        parent[ra] = rb;
    } else if (rank[ra] > rank[rb]) {
        parent[rb] = ra;
    } else {
        parent[rb] = ra;
        ___;
    }
}