并查集深度学习：从理论起源到核心图解

库玛西

815人浏览 · 2026-05-22 15:21:44

库玛西 · 2026-05-22 15:21:44 发布

文章目录

阶段 1：起源与逻辑 —— 为什么需要并查集？
阶段 2：基础代码实现 —— 朴素森林的构建与“找祖先”
阶段 3：高级优化 —— 路径压缩与按秩合并
阶段 3.5 按秩合并（Union by Rank）
阶段 4：进阶变种 —— 扩展域并查集与带权并查集

阶段 1：起源与逻辑 —— 为什么需要并查集？

【白话/场景化入门】

想象你在运营一个庞大的“情报朋友圈”。刚开始，所有人都是孤立的。现在有两类操作频繁发生，且数据量高达 10万 级别：

合并（Union）：拉帮结派。“张三”和“李四”结拜了，意味着张三的朋友圈和李四的朋友圈彻底合并成一个大帮派。
查询（Find）：江湖盘问。“王五”和“赵六”是不是同一个祖师爷罩着的？他们属于同一个帮派吗？

为什么传统方法会让你痛苦？

做法 A（暴力染色法）：给每个人贴一个帮派标签。查询两人是否同帮派只需 $O (1)$ 。但是！一旦两个上万人的大帮派合并，你必须把其中一个帮派的所有人都拉出来，挨个修改他们的标签，合并复杂度高达 $O (N)$ 。在10万级数据下，直接卡死。
做法 B（图论建图法）：每次结拜就连一条边，查帮派就跑一次 DFS 或 BFS。合并是 $O (1)$ 了，但每次盘问你都要漫山遍野地去搜寻路径，单次查询最高需要 $O (N)$ 复杂度。

并查集的救命之处：
它打破了这种顾此失彼的僵局。它让帮派内部形成一个“树状金字塔”。每个人不记帮派名字，只记“我的上司是谁”。查询时，顺着上司一路往上查，直到找到那个不用向任何人汇报的“最高帮主（根节点）”。如果两个人的最终帮主是同一个人，那他们就是同门！合并时，更不需要动用所有人，只需要让帮主 A 屈尊当帮主 B 的下属，一句话，整个组织结构瞬间完成合并！

【核心图解】

假设江湖上有 1, 2, 3, 4, 5 五个独立个体。

1. 初始状态（各自为战）：
每个人都是自己的帮主，指针指向自己。

  [1]      [2]      [3]      [4]      [5]
  ↺        ↺        ↺        ↺        ↺

2. 发生合并：1和2结拜，3和4结拜：
2 的上司指向 1；4 的上司指向 3。

    [1]      [3]      [5]
    /        /        ↺
  [2]      [4]

3. 发生进一步合并：让 2 和 4 结拜（即合并两个帮派）：
算法不会直接去动 2 和 4，而是顺着它们去找到各自的最高帮主 1 和 3。然后让 3 认 1 做上司。

        [1]           [5]
       /   \          ↺
     [2]   [3]
           /
         [4]

此时若查询：4 和 2 是否属于同门？

4 往上找：4 $\rightarrow$ 3 $\rightarrow$ 1（帮主是1）
2 往上找：2 $\rightarrow$ 1（帮主是1）
帮主相同，返回 true。整个过程完全不需要遍历所有人！

【保姆级实现】

在竞赛和工业落地中，我们通常使用一个极其紧凑的数组 parent（或简写为 fa）来表达这种树状双亲拓扑结构。以下是无任何寒暄的最简概念 Demo：

#include <iostream>
#include <vector>

// 这是一个展示并查集底层“双亲表示法”映射的数据结构
class DisjointSetConcept {
public:
    std::vector<int> fa;

    // 初始化：刚开始每个人都是自己的上司（帮主）
    void init(int n) {
        fa.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            fa[i] = i; // fa[i] == i 说明 i 是根节点（最高帮主）
        }
    }
    
    // 注意：本阶段仅为起源概念展示，未做任何算法优化
};

int main() {
    DisjointSetConcept dsu;
    dsu.init(5);
    // 此时 fa 数组为: [0, 1, 2, 3, 4, 5] (0号弃用)
    std::cout << "3号的上司是: " << dsu.fa[3] << std::endl; 
    return 0;
}

阶段 2：基础代码实现 —— 朴素森林的构建与“找祖先”

【白话/场景化入门】

在上一阶段，我们理清了“拉帮结派”的逻辑。这一阶段，我们要正式用代码把这套规则落到计算机的底层。
在算法竞赛中，我们要写出能真正运转的“帮派联络机制”。

初始化就像是开局每个人发一块令牌，上面写着自己的名字，代表自己是独立帮主。
查找祖先就像是一层层打电话往上请示：“喂，我的上司是老王，老王的上司是老张……直到电话打到某个不挂电话的‘真大老’那里。”
合并就是真大老之间谈妥了，A 集团的董事长直接宣布：“从今天起，我听 B 集团董事长的！”

我们需要将这套看似复杂的行政链条，用区区十几行代码、两三个最精简的函数表达出来。

【核心图解】

在未做优化的树状结构中，执行 find(4) 的递归弹栈链条如下：

【内存结构】               【递归流向 (fa[x])】
    [1] (根)  <----------  find(1) 返回 1 (fa[1] == 1)
     ▲                        ▲
     |                        |
    [2]       <----------  find(2) 询问 fa[2]
     ▲                        ▲
     |                        |
    [3]       <----------  find(3) 询问 fa[3]
     ▲                        ▲
     |                        |
    [4]       <----------  find(4) 触发调用

当我们要合并 find(4)（根为1）和 find(5)（根为5）所在的树时，合并逻辑是：
让 5 的根节点指向 1 的根节点（即 fa[5] = 1）。

        [1]
       /   \
     [2]   [5]  <-- 5号直接挂到了1号下面！
     /
   [3]
   /
 [4]

【保姆级实现】

这是算法竞赛及工业落地中最朴素、未加特殊优化的标准并查集类实现（最简 Demo）。请仔细观察每一行关键语法：

#include <iostream>
#include <vector>

class PureDisjointSet {
private:
    std::vector<int> fa;

public:
    // 1. 初始化：预分配空间并给 fa[i] 赋值为 i
    void init(int n) {
        fa.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            fa[i] = i; 
        }
    }

    // 2. 查找（Find）：沿着双亲指针递归向上寻找根节点
    int find(int x) {
        if (fa[x] == x) {
            return x; // 找到根节点，它是整个集合的唯一标识（代表元）
        }
        return find(fa[x]); // 关键：未优化前，纯靠递归盲目向上爬
    }

    // 3. 合并（Union）：合并两个元素所在的集合
    void merge(int x, int y) {
        int rootX = find(x); // 先找到 x 的最高帮主
        int rootY = find(y); // 再找到 y 的最高帮主
        
        if (rootX != rootY) { // 如果不在同一个帮派
            fa[rootX] = rootY; // 关键语法：让 x 的帮主 认 y 的帮主为上司
        }
    }
};

int main() {
    PureDisjointSet dsu;
    dsu.init(5);
    dsu.merge(4, 3);
    dsu.merge(3, 2);
    
    if (dsu.find(4) == dsu.find(2)) {
        std::cout << "4和2已经是同门了！" << std::endl;
    }
    return 0;
}

⚠️ 避坑指南（魔鬼细节）

别看这段代码跑得通，在真正的海量数据面前，这个朴素写法是一个巨大的地雷。
如果用户给出的合并请求是：merge(1, 2), merge(2, 3), merge(3, 4)…
这棵树就会退化成一条极其冗长的“单链表”（类似一条竹竿）。
此时，每一次执行 find() 函数，时间复杂度会直接劣化到 $O (N)$ 。如果有 $M$ 次查询，总复杂度会飙升到 $\times M)$ 。在竞赛中这会直接导致 TLE（超时崩溃）！

要想压榨到极致性能，我们需要在“找祖先”和“合并”的时候施加魔法。

阶段 3：高级优化 —— 路径压缩与按秩合并

【白话/场景化入门】

在上个阶段我们提到，如果合并请求很极端，树就会退化成一根长长的“单链表（竹竿）”。每次查祖先都要走十几步，这太愚蠢了。

优化 1：路径压缩（一劳永逸）
既然我们的终极目标只是想知道“最高帮主（根节点）是谁”，那中间那些密密麻麻的“小上司”真的有必要存在吗？
路径压缩的逻辑是：当 4 号顺着 3 $\rightarrow$ 2 $\rightarrow$ 1 这条长线好不容易找到最高帮主 1 之后，4 号不傻，它在退出递归时顺手做一件事——把沿途遇到的 3 号、2 号甚至它自己，全都直接认 1 号为直接上司！
下次 4 号再想找帮主，或者 3 号想找帮主，只需要走 1 步。竹竿瞬间变成了扁平的“扇形辐射结构”！

优化 2：按秩合并（强强联合的策略）
如果两个帮派要合并，一个是拥有 1 万人的庞大帝国（树很深），另一个是只有 2 个人的小团伙（树很浅）。
如果让大帝国的皇帝去当小团伙老大的下属，那这一万人在查询时，路径全部都要加深一层！
按秩合并就是立规矩：矮树必须无条件合并到高树下，或者小树无条件合并到大树下，确保树的高度不会爆炸式增长。

【核心图解】

1. 路径压缩的底层形变：

当我们在一条退化的“竹竿树”上调用经过路径压缩的 find(4) 时：

【优化前：修长竹竿】               【优化后：瞬间扁平化】
        [1] (根)                           [1] (根)
         ▲                               /  |  \
         |                             [2] [3] [4]
        [2]
         ▲
         |
        [3]                     关键：4, 3, 2 在递归弹栈时
         ▲                           直接将指针死死戳在 1 上！
         |
        [4] <-- 执行 find(4)

【保姆级实现】

在算法竞赛（蓝桥杯、ACM）中，“路径压缩”是必写优化，而“按秩合并”由于会增加代码量，且在路径压缩存在时对性能的提升非常微弱，因此竞赛界通常只写路径压缩。

下面给出竞赛中最高效、最精简的完全优化模板。注意看 find 函数的这一行经典的“一行流”写法：

#include <iostream>
#include <vector>

class OptimizedDisjointSet {
private:
    std::vector<int> fa;

public:
    void init(int n) {
        fa.resize(n + 1);
        for (int i = 1; i <= n; ++i) fa[i] = i;
    }

    // ⭐ 核心火力点：带路径压缩的 Find 函数（工业级最优写法）
    int find(int x) {
        // 这行代码利用了 C++ 的赋值运算符右结合性及递归弹栈
        // fa[x] = find(fa[x])：在找到根节点后，回溯时把沿途所有节点的直接上司Fa全部改成根节点
        return fa[x] == x ? x : (fa[x] = find(fa[x]));
    }

    void merge(int x, int y) {
        int rootX = find(x); // 内部自带路径压缩
        int rootY = find(y);
        if (rootX != rootY) {
            fa[rootX] = rootY; 
        }
    }
};

🧠 专家视角：反阿克曼函数的物理奇迹

一旦你加上了路径压缩，并查集的时间复杂度会发生质的飞跃。每次操作的平均时间复杂度将降到 $O(\alpha(N))$ 。
这里的 $\alpha$ 是反阿克曼函数。这个函数增长极其极其缓慢！缓慢到什么程度？
当 $N$ 等于宇宙中已知的所有原子总数时， $\alpha(N)$ 的值也不会超过 5！
所以在工业界和竞赛界，我们直接认为：带路径压缩的并查集，单次操作的时间复杂度就是 $O (1)$ （常数级）。

阶段 3.5 按秩合并（Union by Rank）

🎯 本节专项学习目标

彻底分清按秩合并的两种度量标准：按深度（Height/Rank）与按大小（Size）。
深刻理解为什么有了“路径压缩”后，在某些高级算法（如：可撤销并查集、线段树分治）中必须强制使用“按秩合并”。
掌握纯正的按秩合并保姆级代码。

【白话/场景化入门】

前面我们说过，普通的合并是盲目的（比如直接 fa[rootX] = rootY）。这会导致什么恶果？
想象有两个家族要合并：

A家族（树高/秩为 4）：组织架构很深，老祖宗下面有重孙。
B家族（树高/秩为 1）：总共就 1 个人。

如果你盲目地让 A 家族的老祖宗去认 B 家族的独苗当爹（fa[rootA] = rootB），那么原来 A 家族里的所有人，在查祖先时路径全部要白白加深 1 层！如果反过来，让 B 家族的独苗认 A 家族老祖宗当爹，B 家族只有 1 个人路径加深，A 家族成千上万人的路径长度保持不变。

按秩合并的内核：合并时，矮树（或小树）必须无条件挂到高树（或大树）的根节点下，死死地将整棵森林的深度锁死在 $O(\log N)$ 级别。

【核心图解】

两种“秩（Rank）”的维护策略：

1. 按大小合并（Size）：`size[i]` 记录以 `i` 为根的树中总共有多少个节点。

  【树 X (Size=4)】      【树 Y (Size=2)】            【正确合并：小挂大】
       [rootX]               [rootY]                     [rootX]
       /  |  \                  │                        / | \  \
     [a] [b] [c]               [d]                     [a][b][c][rootY]
                                                                   │
                                                                  [d]
                                                     (所有节点在X下，总Size=6)

2. 按深度合并（Rank）：`rank[i]` 记录以 `i` 为根的树的最大高度。

  【树 X (Rank=3)】      【树 Y (Rank=2)】            【正确合并：矮挂高】
       [rootX]               [rootY]                     [rootX]
         │                     │                         /     \
        [a]                   [b]                    [a]     [rootY]
         │                                            │         │
        [c]                                          [c]       [b]
                                                 (整棵树的最大高度依然是3！)

关键细节：当且仅当两棵树的 rank 完全相同时，矮树挂到高树下才会迫使高树的深度 +1。

【保姆级实现】

以下是经典的按深度（Rank）合并的标准类实现：

#include <iostream>
#include <vector>
#include <algorithm>

class RankDisjointSet {
private:
    std::vector<int> fa;
    std::vector<int> rank; // rank[i] 表示以 i 为根的树的高度

public:
    void init(int n) {
        fa.resize(n + 1);
        rank.assign(n + 1, 1); // 刚开始每个人都是独立的树，高度为 1
        for (int i = 1; i <= n; ++i) fa[i] = i;
    }

    // 注意：此处展示纯正的按秩合并，暂不加路径压缩，以便你观察 rank 的真实变化
    int find(int x) {
        return fa[x] == x ? x : find(fa[x]);
    }

    // ⭐ 核心火力点：按秩合并的 Merge 函数
    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            // 策略：矮树挂到高树下
            if (rank[rootX] < rank[rootY]) {
                fa[rootX] = rootY; // rootX 较矮，挂到 rootY 下，rootY 的总高度不变
            } 
            else if (rank[rootX] > rank[rootY]) {
                fa[rootY] = rootX; // rootY 较矮，挂到 rootX 下，rootX 的总高度不变
            } 
            else {
                // 两树一样高，谁挂谁都行，但被挂的那个树（新根）高度必须 +1
                fa[rootX] = rootY;
                rank[rootY]++; // rootY 成为了新的最高领袖，高度随之加 1
            }
        }
    }
};

🧠 专家视角：为什么竞赛选手平时不写，但高端局必须死磕它？

在普通的比赛中，选手通常只写路径压缩，不写按秩合并。因为单写路径压缩，均摊复杂度就已经达到极其恐怖的 $O(\alpha(N))$ 了，多写一个按秩合并在耗时上几乎没有区别，还会增加代码量。

但是！在高端局中，有一个致命的场景会让你不得不放弃路径压缩，从而只能依赖按秩合并：

当题目要求实现 “可撤销并查集” 或者配合 “线段树分治” 时，我们需要支持回滚操作（也就是把刚刚合并的两个人断开，恢复历史状态）。

路径压缩的死穴：路径压缩是一次性的“毁灭性改造”，弹栈时直接把沿途所有的边全部砍断连到根上，这会导致原有的树形拓扑结构彻底丢失，你根本没办法完美撤销、恢复历史。
按秩合并的救命之处：它没有破坏原本的树形拓扑，每次合并只是在两个根节点之间连了一条边。我们只需要用一个 std::stack 记录下刚刚改动了哪个位置的 fa 和 rank，撤销时直接弹栈把那条新边擦掉，就能在 $O (1)$ 时间内精准回滚！

所以在不能使用路径压缩的高端局，为了确保树的深度不会退化成单链表，按秩合并（或按大小合并）是锁死 $O(\log N)$ 时间复杂度的唯一物理外挂。

教官立刻修正！这次我们撕掉所有可能对小白读者产生时序误导的文字，用最严谨的 LaTeX 数学语言、清晰标注的语言标签以及绝对无歧义的时序警告提示块，重新为你提炼生成的【阶段 4：进阶变种 —— 扩展域并查集与带权并查集】完全体无死角博客底稿。

可以直接完整替换进你的 Markdown 博客源码中：

阶段 4：进阶变种 —— 扩展域并查集与带权并查集

【白话/场景化入门】

之前的三个阶段，并查集只能解决“连通性（是否是同门）”问题，也就是说，它的边是不带任何信息的。但在另一些高端局中题目会迎来颠覆性升级：

带权并查集（不仅同门，还要论资排辈）：
不仅要告诉你张三和李四在同一个帮派，还要记录“张三比李四高 2 个辈分”，或者“张三距离帮派总部有 5 里的距离”。也就是说，树上的每条边都被赋予了一个权重。我们在查找和合并的时候，除了要改写父亲指针，还要完成权重的物理累加与时序更新。
扩展域并查集（敌人的敌人就是朋友）：
在一个充斥着“朋友”与“敌人”的江湖里，游戏规则变复杂了。如果 A 和 B 是敌人，B 和 C 是敌人，那么按照江湖规矩，A 和 C 就是朋友。并查集只能处理连通（朋友），怎么处理排斥（敌人）呢？
答案是：“影分身之术”。把每个人拆成两个虚空阵营：一个代表“我加入朋友阵营”，一个代表“我加入敌人阵营”。这样就把复杂的排斥关系，神不知鬼不觉地转变成了并查集的标准一维连通逻辑！

【核心图解与数学推导】

1. 带权并查集（以维护“节点到根节点的相对差值”为例）

带权并查集的核心，在于维护一个额外的数组 weight[]（存储当前节点到其直接父亲 fa[x] 的相对权值）。

核心魔鬼公式 1：Find（路径压缩）时的权值延迟叠加

当我们在一条退化的带有权值的树链上执行 find(x) 时：

物理向量叠加原理：
在递归向上抓到 root 弹栈回溯时，x 的直接父亲由 fa 变成了 root。根据向量平移：

$\text{x 到 root 的距离} = \text{x 到 fa 的距离} + \text{fa 到 root 的距离}$

由此得出 Find 权值更新公式：

$old_fa ] \text{weight}[x] = \text{weight}[x] + \text{weight}[\text{old\_fa}]$

🚨 骨灰级时序死穴：为什么权值更新必须“先记录、再递归”？
请死死盯住下方保姆级代码里的 find 实现。千万不要自作聪明去调换代码的时序！
我们必须采用 “向量延迟叠加战术”。因为在执行 fa[x] = find(old_fa) 的递归过程中，底层发生了惊天动地的路径压缩。
当递归探底、弹栈回来的一瞬间，你的旧父亲 old_fa 身上的权值 weight[old_fa] 已经抢先一步被刷新成了 “旧父亲到最终根节点（root）的最新距离”。而此时，你的 weight[x] 还是原始的“自己到旧父亲的距离”。
如果你没有使用局部变量 int old_fa = fa[x]; 提前把旧父亲锁定，而是写成了 fa[x] = find(fa[x]); weight[x] += weight[fa[x]];，那么在加和的时候，fa[x] 早已经变成了 root，你加上的将是 weight[root]（其值永远为 0），你的相对数据链条将瞬间发生严重的物理位移与逻辑断裂！必须先记录旧父亲，再递归压扁，最后回溯叠加！

核心魔鬼公式 2：Merge（合并两棵树）时的边权计算

假设我们收到情报：“ $x$ 比 $y$ 大 $s$ 岁”（即 $x - y = s$ ）。此时 $x$ 的根节点是 $\text{rootX}$ ， $y$ 的根节点是 $\text{rootY}$ 。我们要执行 fa[rootX] = rootY。

通过回路的向量封闭性方程：

$\text{weight}[x] + \text{weight}[\text{rootX}] = s + \text{weight}[y]$

移项得出 Merge 权值计算公式：

$\text{weight}[\text{rootX}] = s + \text{weight}[y] - \text{weight}[x]$

2. 扩展域并查集（影分身空间映射）

如果有 $N$ 个人，我们直接开一个 $2 N$ 大小的一维并查集数组：

$\sim N$ 空间：代表“朋友域”（我跟谁是朋友）。
$\sim 2N$ 空间：代表“敌人域”（我跟谁是敌人）。

已知 A 和 B 是敌人 ───►  让 A 的朋友域 连通 B 的敌人域 (merge(A, B + N))
                        让 B 的朋友域 连通 A 的敌人域 (merge(B, A + N))

此时如果再来情报：B 和 C 也是敌人 ───► 让 B 的朋友域 连通 C 的敌人域 (merge(B, C + N))
                                     让 C 的朋友域 连通 B 的敌人域 (merge(C, B + N))

【最终数论闭环】：此时查询 A 和 C 的朋友域 (find(A) == find(C)) 
你会震惊地发现：他们已经自动相连了！“敌人的敌人是朋友”在扩展域里自动闭环！

【保姆级实现】

模板 A：带权并查集标准高分模板（数值差值维护）

#include <iostream>
#include <vector>

class WeightedDSU {
private:
    std::vector<int> fa;
    std::vector<int> weight; // 核心：维护当前节点到其直接父亲的相对差值

public:
    void init(int n) {
        fa.resize(n + 1);
        weight.assign(n + 1, 0); // 刚开始各自独立，到自己的差值都是 0
        for (int i = 1; i <= n; ++i) fa[i] = i;
    }

    // ⭐ 火力点 1：时序安全的带权路径压缩 Find 
    int find(int x) {
        if (fa[x] == x) return x;
        
        int old_fa = fa[x];          // 核心：提前备份路径压缩前的直接父亲
        fa[x] = find(old_fa);        // 1. 递归探底：执行完后，old_fa的weight已被刷新为到根的最新距离
        weight[x] += weight[old_fa]; // 2. 回溯延迟叠加：我到根的距离 = 我到旧父亲距离 + 旧父亲到根的距离
        
        return fa[x];
    }

    // ⭐ 火力点 2：带权合并 Merge (更新连通树新边的权值)
    // 语义：告知系统，x 相对 y 的权值差为 s (即 x - y = s)
    void merge(int x, int y, int s) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            fa[rootX] = rootY; // 将 rootX 树 挂到 rootY 树 下
            // 运用魔鬼公式 2 动态计算并更新新产生的两根节点间的边权
            weight[rootX] = s + weight[y] - weight[x];
        }
    }

    // 战术 API：查询 x 和 y 的相对差值 (x - y)
    bool query_diff(int x, int y, int& result) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) return false; // 不在一个帮派，无法论资排辈
        
        // 都在同一个家族：x - root = weight[x], y - root = weight[y] -> x - y = weight[x] - weight[y]
        result = weight[x] - weight[y];
        return true;
    }
};

模板 B：扩展域并查集标准高分模板（多阵营对立维护）

#include <iostream>
#include <vector>

class ExtensionDSU {
private:
    std::vector<int> fa;
    int n;

public:
    // 关键点：扩展域需要开辟 2 * n 的空间
    void init(int n_size) {
        n = n_size;
        fa.resize(2 * n + 1);
        for (int i = 1; i <= 2 * n; ++i) fa[i] = i;
    }

    int find(int x) {
        return fa[x] == x ? x : (fa[x] = find(fa[x]));
    }

    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) fa[rootX] = rootY;
    }

    // 核心战术 API 1：宣布 x 和 y 是朋友
    void set_friend(int x, int y) {
        merge(x, y);         // 朋友的朋友是朋友 (朋友域融合)
        merge(x + n, y + n); // 敌人的敌人是朋友 (敌人域融合)
    }

    // 核心战术 API 2：宣布 x 和 y 是敌人
    void set_enemy(int x, int y) {
        merge(x, y + n);     // 我的朋友是你的敌人
        merge(y, x + n);     // 你的朋友是我的敌人
    }

    // 核心战术 API 3：判断 x 和 y 是否是朋友
    bool is_friend(int x, int y) {
        return find(x) == find(y);
    }
};