https://labuladong.online/zh/algo/data-structure/union-find/

oboe讲解

你好！我是教练。在刷完了“岛屿系列”的搜索算法后，你一定感觉到：对于某些只关心“谁和谁是一伙的”，而 不关心“具体路径是怎么走的” 的问题，DFS/BFS 显得有些“大材小用”且代码繁琐。

这正是 并查集 (Union-Find) 登场的时刻。labuladong 的这篇文章深入浅出地讲解了并查集的底层逻辑和优化算法。我为你整理了一份金牌竞赛视角的总结：

---

一、 预备知识点

在深入并查集之前，你需要理解：

1. 森林 (Forest)： 并查集的底层结构不是一棵树，而是由多棵树组成的森林。每棵树代表一个连通块。
2. 根节点 (Root)： 每棵树的根节点是这个连通块的“代表（Representative）”。
3. 动态连通性 (Dynamic Connectivity)： 这类问题的核心是两个动作——“连接”和“查询是否连接”。

---

二、 启发式教学：草稿纸上的“江湖门派”

请拿出纸笔，跟我一起构筑这个逻辑模型。

1. 核心数据结构

我们只需要一个数组 parent[]。

• parent[x] = y 意味着：x 的上级是 y。
• 如果 parent[x] == x，意味着：x 就是这个门派的掌门（根节点）。

2. 三大核心操作 (请在纸上画出箭头的指向)

• Find (寻根)： 顺着 parent 数组向上找，直到找到掌门。
• Connected (判同)： 找两个人的掌门，掌门是同一个人，那他们就是同门。
• Union (合并)：
  • 图形操作： 派系 A 的掌门向派系 B 的掌门“投诚”。
  • 代码动作： parent[rootA] = rootB。

---

三、 算法的进化：复杂度优化建议

如果你只是简单地写 parent[rootA] = rootB，在极端情况下（比如 1 连 2，2 连 3...）会退化成一根长链，查找复杂度变成 $O(N)$。在 NOI 竞赛中，这会让你 TLE。

1. 路径压缩 (Path Compression) —— 最高效优化

• 思路： 既然我只关心掌门是谁，那我每次寻根时，顺便把路上遇到的所有人都直接挂到掌门名下。
• 图形变化： 瘦长的“竹竿”瞬间变成矮胖的“扇子”。
• 效果： 查找复杂度近乎 $O(1)$。

2. 按秩合并 (Union by Rank/Size)

• 思路： “小兵从大将”。合并时，把节点数少（或者树高较小）的那棵树挂到大的那棵树下面。
• 效果： 保证树的高度增长尽可能缓慢。

教练提示： 在实际竞赛中，“路径压缩” 是必须写的。如果写了路径压缩，通常不需要再写按秩合并也能过题，除非题目数据极其刁钻。

---

四、 时间与空间复杂度思考

• 空间复杂度： 极优。仅需 $O(N)$ 存储 parent 数组。
• 时间复杂度：
  • 在同时使用路径压缩和按秩合并的情况下，复杂度为 $O(\alpha(N))$。
  • $\alpha$ 是阿克曼反函数。你可以通俗地理解为：对于全宇宙原子数量级的数据，$O(\alpha(N))$ 也不超过 5。这在算法竞赛中被视为常数级别。

---

五、 读题关键词：什么时候该祭出并查集？

在阅读题目描述时，如果出现以下词汇，请在大脑中立刻闪现并查集的模板：

1. “等价关系” (Equivalence Relation)： A 等于 B，B 等于 C，推导出 A 等于 C。
2. “连通块个数” (Number of components)： 询问最后剩几个帮派。
3. “动态增加边”： 图的结构在运行中不断产生新的连接。
4. “最小生成树” (Kruskal 算法)： 这是并查集最经典的工业级应用。
5. “朋友圈/社交网络”： 询问两个人在社交关系中是否可达。

---

六、 教练总结

labuladong 的总结精髓在于：并查集是处理“组队”问题的高射炮。

• 如果你关心的是路径（怎么走的），用 DFS/BFS。
• 如果你关心的是结果（是不是一伙的），用 并查集。

记住并查集的口诀： 初始各自为王，合并首领投降，寻根一路压缩，连通瞬间打方。

下次遇到岛屿数量的问题，你可以尝试不用 DFS，而是遍历每一个陆地格子，把相邻的陆地在并查集中 unite。最后数数 parent 数组里有多少个 parent[i] == i，那也是岛屿的数量！加油！

---

你好！作为教练，我为你准备了一道并查集的**“金牌模板题”**。

在 OI 竞赛中，并查集的第一课通常不是直接做岛屿题，而是这道经典的**“亲戚关系”**（或称“江湖门派”）问题。它能让你最纯粹地练习 find 和 union 操作，而不被复杂的网格坐标干扰。

---

一、 模板例题：江湖门派 (The Gangs)

题目背景： 江湖上有 $N$ 个侠客，初始时他们各不相关。现在江湖上发生了 $M$ 桩事件，每桩事件会告诉你有两位侠客结为了同门。

任务描述：

1. 处理 $M$ 条合并信息：侠客 $X$ 和侠客 $Y$ 结为同门（如果他们已经是同门则忽略）。
2. 在所有事件结束后，请问江湖上一共有多少个独立的门派？

输入格式： 第一行包含两个整数 $N$ 和 $M$ ($1 \le N \le 10^5, 1 \le M \le 2 \times 10^5$)。 接下来 $M$ 行，每行包含两个整数 $X, Y$，表示 $X$ 和 $Y$ 结为同门。

输出格式： 输出一个整数，表示最终门派的总数。

---

二、 预备知识点（核心代码块）

在写这题之前，请在脑海中（或草稿纸上）准备好这三个函数：

1. init(n): 初始化数组，让每个人的上级都是自己。
2. find(x): 寻找 $x$ 的最终掌门，必须包含“路径压缩”。
3. unite(x, y): 让 $x$ 所在的门派并入 $y$ 所在的门派。

---

一、 样例补充

在开始思考前，我们先看一个直观的例子： 输入：

5 3
1 2
2 3
4 5

样例解释：

1. 初始：有 5 个侠客，每个人自成一派：{1}, {2}, {3}, {4}, {5}。共 5 派。
2. 1 和 2 结盟：派系变为 {1, 2}, {3}, {4}, {5}。共 4 派。
3. 2 和 3 结盟：因为 1 和 2 已是同门，2 和 3 结盟后，1, 2, 3 都在同一派了：{1, 2, 3}, {4}, {5}。共 3 派。
4. 4 和 5 结盟：派系变为 {1, 2, 3}, {4, 5}。共 2 派。 输出：

2

---

二、 预备知识点

要优雅地解决这道题，你需要掌握以下工具：

1. 并查集 (Disjoint Set Union, DSU)：这是处理“合并”与“查询”关系的专属数据结构。
2. 树形结构的基础概念：理解“父亲节点”与“根节点”的关系。
3. 等价关系：理解传递性（A 和 B 同门，B 和 C 同门，则 A 和 C 也是同门）。

---

三、 启发式思路引导：在草稿纸上画出来

现在，请拿出你的草稿纸和笔，跟我一起做以下推演：

1. 初始状态：点

在纸上画 5 个独立的点，编号 1 到 5。

• 思考：现在每个人都是自己的“掌门人”，我们如何记录这个信息？
• 动作：我们可以开一个数组 fa[i]，初始化 fa[i] = i，代表每个人当前的顶头上司就是自己。

2. 处理合并：连线

当事件 1 2 发生时，在 1 和 2 之间画一条线。

• 启发：为了方便管理，我们规定“小弟”要认“大哥”。我们可以让 fa[1] = 2（或者反过来）。
• 动作：在纸上把点 1 的箭头指向点 2。

3. 传递性：找祖先

当事件 2 3 发生时，要把 2 和 3 所在的门派合并。

• 重点：2 的上司可能已经有人了，3 也可能有自己的门派。
• 操作：我们不直接连 2 和 3，而是先去寻找 2 所在门派的“最高领导人”（根节点），再寻找 3 所在门派的“最高领导人”。
• 画图：如果 2 认了 3 做大哥，那么原本 1 的大哥是 2，2 的大哥是 3。1 找最高领导时，会沿着 1 -> 2 -> 3 找到 3。

4. 统计结果：数根

当所有 $M$ 条信息处理完后，观察你的草稿纸。

• 提问：有多少个门派，在图中表现为什么特征？
• 结论：在森林中，根节点（自己是自己上司的点）的数量，就是门派的总数。

---

四、 性能优化思考

1. 时间复杂度分析

• 朴素查找：如果你只是单纯地顺着箭头找祖先，最坏情况下这棵树会退化成一条链（比如 1->2->3->4...->N）。每次查找的时间复杂度是 $O(N)$，总复杂度 $O(M \times N)$。对于 $10^5$ 的数据量，这会超时（TLE）。

2. 优化建议 (OI金牌秘籍)

• 路径压缩 (Path Compression)：在“找祖先”的过程中，顺便把路径上所有人的 fa[i] 直接指向最终的根节点。
  • 图形想象：把原本很高的树“拍扁”，让所有人直接连向掌门。
• 按秩合并 (Union by Rank/Size)：合并时，总是把“矮树”合并到“高树”下面，防止树长得太高。
• 结果：优化后的单次操作平均时间复杂度几乎是常数级 $O(\alpha(N))$，其中 $\alpha$ 是反阿克曼函数，在人类宇宙规模内都不超过 5。

三-1. 启发式引导：草稿纸上的推演

假设 $N=5$（侠客 1, 2, 3, 4, 5），事件如下：

1. unite(1, 2)
2. unite(3, 4)
3. unite(2, 4)

请跟我一起在纸上画出 fa 数组的变化：

1. 初始状态： fa: [1, 2, 3, 4, 5] （每个人都是掌门，共 5 个门派）

2. 事件 1 (1, 2)： 让 1 的掌门指向 2。 fa: [2, 2, 3, 4, 5] （门派数：4）

3. 事件 2 (3, 4)： 让 3 的掌门指向 4。 fa: [2, 2, 4, 4, 5] （门派数：3）

4. 事件 3 (2, 4)： 找到 2 的掌门是 2，4 的掌门是 4。让 2 指向 4。 fa: [2, 4, 4, 4, 5] （门派数：2）

提问： 此时执行 find(1) 会发生什么？

• 路径压缩前： 1 $\to$ 2 $\to$ 4。
• 路径压缩后： 1 直接指向 4。下一次再查 1，瞬间就能知道掌门是 4。

---

三-2. 时间与空间复杂度思考过程

• 时间复杂度：
  • 如果没有路径压缩，最坏情况是 $O(N \cdot M)$（退化成链）。
  • 加上路径压缩： 均摊复杂度为 $O(M \cdot \alpha(N))$。对于 $10^5$ 的数据，处理 $2 \times 10^5$ 次合并仅需几十毫秒。
• 空间复杂度：
  • 只需要一个 fa 数组，$O(N)$。

---

四、 模板思路提示（伪代码/逻辑流）

graph TD
    A("开始: N=5, M=3, ans=N") --> B("初始化: fa[i] = i")
    B --> C("读入 X, Y")
    C --> D{"find(X) == find(Y)?"}
    D -- "否 (不是同门)" --> E("unite(X, Y): fa[rootX] = rootY")
    E --> F("ans 减 1")
    D -- "是 (已是同门)" --> G("跳过")
    G --> H("所有 M 条处理完?")
    F --> H
    H -- "否" --> C
    H -- "是" --> I("输出 ans")

---

五、 读题关键词：识别并查集模板

在读题时，看到这些描述，基本可以确定是并查集模板题：

1. “传递性”：如果 A 与 B 相关，B 与 C 相关，则 A 与 C 相关。
2. “集合合并”：原本分散的个体，因为某些关系被强行凑成一堆。
3. “统计连通块数量”：询问最后剩几堆，或者某个堆里有多少人。
4. “动态查询”：在合并的过程中，随时可能问你“这两个人现在认识吗？”

教练寄语： 这道题是并查集的“根”。无论是后来我们要做的“岛屿数量”（用并查集版），还是复杂的“种类并查集”、“带权并查集”，所有的变化都建立在 find 和 union 这两个动作之上。先把这个简单的“掌门找人”逻辑写熟练吧！加油！

---

并查集模板 傻瓜版（未优化）

#include <bits/stdc++.h>
using namespace std;

struct dsu{
    vector<int> fa;
    dsu(int n){
        fa.resize(n);
        for(int i=0;i<n;i++){
            fa[i]=i;//每个点的父节点都是自己
        }
    }


    //注意命名不用union因为union是c++关键字
    void unite(int x,int y){
        //合并操作  傻瓜版
        int rootx = find(x);
        int rooty = find(y);
        fa[rootx] = rooty;
    }
    int find(int x){
        //非递归查找 傻瓜版
        int root = x;//设置从x开始查找根节点root
        // 第一次遍历：找到根节点
        while (fa[root] != root) {
            root = fa[root];
        }
        return root;
    }
};

int main(){
    dsu d(5);
    d.unite(0,1);
    d.unite(1,2);
    cout<<d.find(0)<<endl;
    cout<<d.find(1)<<endl;
    cout<<d.find(2)<<endl;
    cout<<d.find(3)<<endl;
    cout<<d.find(4)<<endl;
}

并查集模板 优化版（按rank合并、路径压缩）

#include <bits/stdc++.h>
using namespace std;

struct dsu{
    vector<int> fa;
    vector<int> rank;
    dsu(int n){
        fa.resize(n);
        rank.resize(n, 1);
        for(int i=0;i<n;i++){
            fa[i]=i;//每个点的父节点都是自己
        }
    }

    //注意命名不用union因为union是c++关键字
    void unite(int x,int y){
        //带秩优化的合并操作
        int rootx = find(x);
        int rooty = find(y);
        if(rootx!=rooty){
            // 将秩较小的树合并到秩较大的树上
            if(rank[rootx] < rank[rooty]){
                fa[rootx] = rooty;
            }else if(rank[rootx] > rank[rooty]){
                fa[rooty] = rootx;
            }else{
                // 秩相等时，合并后秩加1
                fa[rootx] = rooty;
                rank[rooty]++;
            }
        }
    }
    int find(int x){
        //带路径压缩的非递归查找
        int root = x;//设置从x开始查找根节点root
        // 第一次遍历：找到根节点
        while (fa[root] != root) {
            root = fa[root];
        }
        // 第二次遍历：路径压缩，将路径上所有节点直接连接到根节点
        while (fa[x] != root) {
            int next = fa[x];
            fa[x] = root;
            x = next;
        }
        return root;
    }
};

int main(){
    dsu d(5);
    d.unite(0,1);
    d.unite(1,2);
    cout<<d.find(0)<<endl;
    cout<<d.find(1)<<endl;
    cout<<d.find(2)<<endl;
    cout<<d.find(3)<<endl;
    cout<<d.find(4)<<endl;
}