并查集（Union Find）

"判断两个东西在不在同一组" 这一族题——朋友圈、岛屿合并、账户合并、等式约束——你用 BFS / DFS 也能解，但有个数据结构专门为它而生：并查集（Union Find，又叫 DSU）。

一句话框架：parent 数组指向"代表元"，find 跟着 parent 跳到根，union 把两个根接起来。加上路径压缩，平均 O(1) 回答连通性查询。

一个常见类比：并查集就像家族族长——只需知道你的族长是谁，同族长就是同家族。合并两个家族时让一边的族长认另一边当老大，不用动每个成员。

本章从 LC 547 切入对比 DFS 和并查集，再给出模板，最后串讲常见变体。

1. 核心原理

并查集（Union Find，又称 Disjoint Set Union, DSU）维护一族互不相交的集合，并对外暴露两个操作：find(x) 返回 x 所在集合的代表元（"根"），union(x, y) 合并 x 和 y 所在的两个集合。判断"x 与 y 是否在同一组"只需比较 find(x) == find(y)。

每个集合内部组织成一棵有根树：每个节点用一个 parent[x] 指针指向其父亲，根节点 parent[root] = root。初始时 parent[i] = i，每个元素自成一组。find 沿 parent 链向上一直走到根，union 把一棵树的根挂到另一棵树的根下面。

加上"路径压缩"与"按秩合并"两项优化后，单次操作的摊还复杂度为 O(α(n))——其中 α 为反 Ackermann 函数，增长极慢，对所有现实规模 n ≤ 2⁶⁵⁵³⁶ 都有 α(n) ≤ 5，工程上可视为常数。

暴力为什么不够

朴素地用 DFS/BFS 答连通性也能写：每次询问跑一遍 O(n + m)。但只要题目要求"边在线一条一条流入"或者"边按权值阈值动态生效"，DFS 每次询问都得重跑整张图。LC 547 这种 n = 200 的小数据不会爆，但 LC 1697（n ≤ 10⁵、查询 q ≤ 2 × 10⁴）走 DFS 是 O((n + m) · q)，必 TLE。

DFS：边集是只读快照、每次查询独立从头跑
        →  无法 O(α(n)) 在线维护连通性

并查集：parent 数组随加边演化、每次合并/查询都摊还 O(α(n))
        →  天然支持流式/在线连通性查询

定位差别一句话：DFS 是离线一次性工具，并查集是在线可维护数据结构。

核心 invariant 与两项关键优化

并查集的全部正确性来源于一个简单 invariant：两个元素在同一集合 ↔ 沿 parent 链向上能到达同一个根。所有操作的目标都是维护这个等价关系。

不加优化时，union 直接把一根挂到另一根，最坏会把树拉成一条长 O(n) 的链——单次 find 退化为 O(n)。两项必装优化把它压回近常数：

路径压缩（Path Compression）：find(x) 沿链向上走到根的过程中，把链上的节点直接挂到根。下次再 find 同一节点，一步到根。

find(4) 前：              find(4) 后（路径压缩到根）：

      1                          1
      │                       / / \ \
      2                      2 3 4  ...
      │
      3
      │
      4

实现上两种风格：

• 递归完全压缩：find(x) 递归到根，回溯时把每个节点的 parent 直接赋为根。代码最短，但 Python 默认递归深度 1000，长链会爆栈。
• 路径折半（path halving）：迭代版，每走一步令 parent[x] = parent[parent[x]]、再令 x = parent[x]。代码紧凑、不递归，实测和完全压缩几乎同速。

工程上更推荐路径折半：不爆栈、跑得快。模板就用它。

按秩合并（Union by Rank/Size）：合并两棵树时，把矮（小）的挂到高（大）的下面，避免树高单调上升。维护 rank[x] 或 size[x]：

• 两树高度不同：矮的挂到高的，整体高度不变。
• 两树高度相同：随便挂一边，被挂侧的高度 +1。

合并 height=1 的 A 与 height=2 的 B：

A:     B:           合并后：
 a      b              b
        │             / \
        c           c    a    （高度仍是 2，不增）

按秩合并即使不加路径压缩，单次 find 也能压到 O(log n)；与路径压缩联用，单次操作摊还 O(α(n))。

α(n) 是什么

α 是反 Ackermann 函数，增长极慢：

可观测宇宙原子数约 10⁸⁰ ≈ 2²⁶⁶，远不到 α(n) = 5 的阈值。所以工程上把 O(α(n)) 直接当 O(1) 用。

三档复杂度对比

要严格证明 α(n) 摊还，需要同时启用路径压缩和按秩合并。单独使用任一项的 bound 也值得知道：

实测 n = 10⁶, m = 5 × 10⁶ 规模下：朴素约 30 秒级、只按秩约 1 秒级、联合优化约 100 毫秒级。多数 LeetCode 题写到"只路径压缩 + 按 size 合并"已够用，但工业代码两项都加是稳妥默认。

模板要素一张表

size vs rank 的取舍：size 同时回答了"x 所在分量多大"这个常见追问（LC 1101 / 1631 都要），rank 只在合并时更新、读起来无意义。模板默认用 size。

2. 通用模板

下面给"路径折半 + 按 size 合并 + 维护分量数"的标准版。三种语言接口一致：find(x)、union(x, y)（C++ 因 union 是关键字改名 unite）、connected(x, y)、count。

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))                  # parent[i] = i：每人自成一组
        self.size = [1] * n                           # 分量大小（小挂大用）
        self.count = n                                # 当前分量数

    def find(self, x: int) -> int:
        # 路径折半：每走一步直接跳到 parent[parent[x]]
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                              # 已同组，本次未合并
        if self.size[rx] < self.size[ry]:             # 按 size 合并：小挂大
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        self.count -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

class UnionFind {
    private final int[] parent;
    private final int[] size;
    private int count;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;                            // 自成一组
            size[i] = 1;
        }
        count = n;
    }

    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];            // 路径折半
            x = parent[x];
        }
        return x;
    }

    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;                   // 已同组
        if (size[rx] < size[ry]) {                    // 小挂大
            int tmp = rx; rx = ry; ry = tmp;
        }
        parent[ry] = rx;
        size[rx] += size[ry];
        count--;
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int getCount() { return count; }
}

class UnionFind {
    vector<int> parent;
    vector<int> sz;
    int count;

public:
    UnionFind(int n) : parent(n), sz(n, 1), count(n) {
        iota(parent.begin(), parent.end(), 0);        // parent[i] = i
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];            // 路径折半
            x = parent[x];
        }
        return x;
    }

    bool unite(int x, int y) {                        // C++ union 是关键字，改名 unite
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (sz[rx] < sz[ry]) swap(rx, ry);            // 小挂大
        parent[ry] = rx;
        sz[rx] += sz[ry];
        count--;
        return true;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

    int getCount() const { return count; }
};

几个工程细节：

• union 返回 bool 表示是否真正合并：返回 false 即"调用前 x、y 已经在同一组"。LC 684 这类"找冗余边"题直接靠返回值定位多余边——见 §4.2。
• count 字段在初始化时设为 n，每次成功合并减 1：LC 547 / 200 这类"数连通分量"题 O(1) 读出。注意它是派生量，外部直接改 parent 会让 count 失同步；调试时可用 sum(1 for i in range(n) if uf.find(i) == i) 重算一次确认。
• size vs rank：模板用 size，能顺手回答"x 所在分量多大"。极致追求常数可改 rank（仅合并时更新），但实测差异微乎其微。
• 附加信息只在根节点上有效：若要维护"分量最大权"等附加字段，必须在 union 里同步更新到新根。读取时先 find 到根再读，非根节点的字段是过期值。
• 总复杂度：n 个节点、m 次 find/union，摊还总复杂度 O((n + m) α(n))，几乎线性。

3. 母题精讲

LeetCode 547. 省份数量

链接：LeetCode 547

题意：有 n 个城市，给一个 n × n 的对称邻接矩阵 isConnected，isConnected[i][j] = 1 表示城市 i 和 j 直接相连。如果两个城市可以通过若干条直接相连的边互达，它们就属于同一个"省份"。返回不同省份的数量。

数据范围：

• n：1 到 200
• isConnected[i][j]：0 或 1，且 isConnected[i][i] = 1、矩阵对称

示例：

输入：isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]
输出：2
解释：城市 0 和 1 互通，构成一个省份；城市 2 自成一省。

DFS 解法（复用网格图的思路）

看过本站 网格图 · DFS / BFS 基础 那一章的话，对这种"数连通分量"题应该已经条件反射——把每个城市当节点，相邻矩阵当邻接表，对每个未访问的节点跑一次 DFS、染色掉整个分量，外层 for 数一下就行。

class Solution:
    def findCircleNumDFS(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        count = 0

        def dfs(i):
            visited[i] = True
            for j in range(n):
                if isConnected[i][j] == 1 and not visited[j]:
                    dfs(j)

        for i in range(n):
            if not visited[i]:
                count += 1
                dfs(i)
        return count

复杂度 O(n²)——外层扫 n 个起点，内层 DFS 每次最坏遍历邻接矩阵一整行，加起来访问邻接矩阵的总次数是 n²。

这份解法没毛病。但它有一个隐含假设：所有边一开始就给好了，可以离线 DFS。换句话说，DFS 只适合"全图已知 + 一次性回答"。但题目稍微变一变就傻眼：

• 边是一条一条来的，每加一条边问"现在有几个连通分量"？
• 想在加边的同时过滤——只有边权 ≤ threshold 的边才算？
• 想知道两点是否连通，但不要求枚举整个分量？

DFS 每次问都要重跑 O(n + m)，太贵。这时就要把"连通性"本身当成一种可维护的数据结构——这就是并查集出场的地方。

同样的题，用并查集怎么写？

并查集的逻辑其实就一句话：每个节点一开始自成一组，对每条边 (i, j)，把 i 所在的组和 j 所在的组合并。最后数一下有多少个"组的根"，就是分量数。

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        parent = list(range(n))                        # 一开始每人自成一派

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]          # 路径压缩（路径折半）
                x = parent[x]
            return x

        def union(x, y):
            rx, ry = find(x), find(y)
            if rx != ry:
                parent[rx] = ry

        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)

        return sum(1 for i in range(n) if find(i) == i)

复杂度也是 O(n²)——主要花在扫邻接矩阵上，并查集本身的 find / union 摊还 O(α(n)) ≈ O(1)，可以忽略。

下面交互演示走一遍 isConnected = [[1,1,0,0,0],[1,1,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,1]] 这个 5 节点例子（上三角边：(0,1)、(1,2)、(3,4)）—— 颜色表示当前所属分量：

光看 LC 547 这一道，并查集似乎没占到便宜。但它的真正威力在两件事上：

1. 在线：边是流式来的，每加一条边都能 O(α(n)) 维护好整体连通性。
2. 可扩展：可以挂额外信息——分量大小、带权关系、按时间撤销等。LC 1697 这种"边按权值过滤后查连通性"的题，DFS 每次询问都重跑就废了；并查集排好序后一路 union 过去，整体 O((n + q) log + α)。

DFS 和并查集都能解 LC 547，但定位不同——DFS 是离线"一次性"工具，并查集是在线"可维护"数据结构。下面 §4 把套路推广到加边检测环（LC 684）与多类约束建模（LC 990）。

4. 例题串讲

按"连通查询 → 加边检测环 → 多类约束建模"递增。每道带一个 follow-up 续到下一题。

4.1 LC 547 省份数量（并查集版）

回到本章开头那道题。完整代码：

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        uf = UnionFind(n)
        for i in range(n):
            for j in range(i + 1, n):                 # 矩阵对称，只扫上三角
                if isConnected[i][j] == 1:
                    uf.union(i, j)
        return uf.count

复杂度 O(n² α(n))——主要花在扫邻接矩阵的 O(n²) 上。

跟开头 DFS 解法比，时间复杂度同阶，但这里有个额外优势：这个写法可以无痛改造成在线版——把 for i, j 循环改成"从外部一条一条 receive 边"的接口，每次 union 完直接读 uf.count 就是当前分量数。DFS 做不到这点——每加一条边都要重新跑一次。

工程实现注意

• 上三角扫描：邻接矩阵是对称的，扫整个矩阵会做两次重复的 union（虽然 union 内部会去重，但浪费时间）。j 从 i + 1 开始更干净。
• uf.count vs 重新扫一遍：维护一个 count 字段比"最后扫一遍数根"更快——O(1) vs O(n)。但忘了维护、或者中途有外部直接改 parent 时，count 就会失同步。这种边角调试时把 count 当成"派生量"重新算一次确认即可：sum(1 for i in range(n) if uf.find(i) == i)。

Follow-up：上面是给整张邻接矩阵后一次性合并。如果题目改成"一条一条加边，每加完一条问当前是不是有环了"——LC 684 这样的题怎么办？

4.2 LC 684 冗余连接

链接：LeetCode 684

题意：给一棵原本是树的图，多加了恰好一条多余的边，使它变成有一个环的图。返回这条多余边。如果有多个答案，返回数组中最后出现的那一条。

数据范围：

• 节点数 n：3 到 1000
• 给的边是 edges[i] = [a, b]，1 ≤ a, b ≤ n，共 n 条边（树是 n - 1 条，加一条变 n 条且必有环）

示例：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]
解释：原本 1-2, 1-3 已经构成一棵树（三节点两边），再加 [2,3] 就形成环 1-2-3-1。

核心思路：union 返回 false 就是冗余边

并查集天生干这个。一条一条加边、每加一条做 union：

• 如果 union(a, b) 返回 true（真的合并了两个原本不同的分量），这条边是树边，继续。
• 如果 union(a, b) 返回 false（a 和 b 已经连通），这条边会新增一个环——它就是冗余的。

题目保证恰好一条多余边、且要返回"数组中最后出现的"那一条，顺序扫一遍 edges，记录最近一次发现的冗余边即可。又因为只有一条多余边，所以发现的第一条冗余边就是答案——直接返回。

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        uf = UnionFind(n + 1)                          # 节点 1..n，多开一格方便索引
        for a, b in edges:
            if not uf.union(a, b):                     # 已连通，加这条边就成环
                return [a, b]
        return []                                      # 题目保证有解，不会到这

复杂度 O(n α(n)) ≈ O(n)——每条边做一次 union，每次摊还常数。

为什么 DFS 在这道题上更别扭

不用并查集也能做：每加一条边 (a, b) 之前，用 DFS / BFS 检查 a 到 b 是否已经可达。如果可达，这条边就是冗余的。但每次检查 O(n)、加 n 条边、整体 O(n²)。

并查集把"加边 + 检查可达"合成一个 O(α(n)) 操作。这就是为什么"边在线流入、需要边加边查连通"的场景几乎是并查集的专属——堆 / 树状数组都干不了这事。

Follow-up：上面是"加边发现环"，处理的是正向约束（这两个点应该连通）。如果题目里还有反向约束（这两个点必须不在同一组），怎么办？

4.3 LC 990 等式方程的可满足性

链接：LeetCode 990

题意：给一个字符串数组 equations，每个字符串是 "a==b" 或 "a!=b" 形式，a 和 b 是小写英文字母。判断是否存在一种字母 → 值的赋值，使所有方程都成立。

数据范围：

• 1 ≤ equations.length ≤ 500
• 字符串只含小写字母和 == / !=

示例：

输入：equations = ["a==b","b!=a"]
输出：false
解释：a == b 要求两者同值，但后面又要求两者不同值，矛盾。

核心思路：先合并 ==，再校验 !=

并查集天然处理"等价类"。== 是等价关系（自反、对称、传递），完全对应"合并到同一集合"。!= 是反等价约束，最后统一检查就行。

两遍扫描套路：

1. 第一遍：处理所有 == 方程，把字母合并到同一组。
2. 第二遍：处理所有 != 方程，检查每对 (a, b) 是否被错误合并——如果 find(a) == find(b)，矛盾，返回 false。

这里有个坑：不能交替处理！如果先看到 a != b、再看到 a == c、b == c，按到达顺序处理就会漏掉矛盾。全部 == 先做完合并，再统一查 !=——分两次扫是这道题的关键。

class Solution:
    def equationsPossible(self, equations: list[str]) -> bool:
        uf = UnionFind(26)                             # 26 个字母

        def idx(c): return ord(c) - ord('a')

        # 第一遍：合并所有 ==
        for eq in equations:
            if eq[1] == '=':
                uf.union(idx(eq[0]), idx(eq[3]))

        # 第二遍：校验所有 !=
        for eq in equations:
            if eq[1] == '!':
                if uf.connected(idx(eq[0]), idx(eq[3])):
                    return False
        return True

复杂度 O(N α(26)) ≈ O(N)，N 是方程数。空间 O(26) = O(1)。

为什么必须两遍

考虑 equations = ["a!=b", "b==c", "a==c"]：

• 单遍处理：a != b（此时 a、b、c 都独立，没矛盾）→ b == c（合并）→ a == c（合并 a、b、c 都到一组，但 != 检查已经过了）。漏报矛盾。
• 两遍处理：先合 b==c、a==c，得到 {a, b, c} 一组 → 再查 a != b，发现 find(a) == find(b)，正确返回 false。

更一般地说：约束分两类时——一类是 "应该满足"（合并），另一类是 "校验"（查询）——先做完所有合并、再统一做查询，这是并查集套路里非常通用的模式。LC 399、LC 1061 都是这个套路的变体。

字母映射的小技巧

ord(c) - ord('a') 把字符映射成 0-25 的整数下标。如果字符集是任意字符串（比如 LC 1061 是任意小写英文单词），就用 dict 做映射；如果只是固定 26 字母，数组下标更快。

5. 坑、易错与复杂度

千万别忘了路径压缩

不加路径压缩、不按秩合并的"裸"并查集，最坏 O(n) 单次 find，整体 O(nm)。LC 547 这种 n = 200 的小数据不会超时，但 LC 1697（n ≤ 10⁵、查询 q ≤ 2 × 10⁴）就会爆。模板里两个优化都加上，是稳妥的默认写法。

路径压缩的两种风格

递归完全压缩 vs 迭代路径折半：

• 递归版：def find(x): return x if parent[x] == x else find(parent[x])（并在返回前赋值 parent[x] = result）。代码最短，但 Python 默认递归深度 1000，长链时会爆栈。
• 迭代版（path halving）：模板里那种 while 循环写法。性能几乎一样，不爆栈。

我个人偏好迭代版，理由就两个：不爆栈、跑得快。

节点编号 0-based vs 1-based

LC 题里两种都有：

• 0-based：LC 547（城市 0..n-1）、LC 200 网格映射等。UnionFind(n) 就够。
• 1-based：LC 684（节点 1..n）、LC 685 等。UnionFind(n + 1)，索引 0 浪费一格，但代码不用写 -1 减法，更不容易出错。

按题目要求选。

多类节点：偏移合并

LC 990 那道题不涉及多类节点，但有一类题（如 paywall 里的 LC 947 移除石头）需要把"行"和"列"当成不同类型的节点放在同一个并查集里。常用做法是编号偏移：行 i 用编号 i，列 j 用编号 j + N。这样所有行、列共用一个并查集，但永远不会撞号。LC 952 / 947 都是这个套路。

维护额外信息的代价

模板里维护了 size 和 count。要维护更多（比如"分量内最大权"、"分量内某属性的和"），就在 union 里同步更新：

def union(self, x, y):
    rx, ry = self.find(x), self.find(y)
    if rx == ry:
        return False
    if self.size[rx] < self.size[ry]:
        rx, ry = ry, rx
    self.parent[ry] = rx
    self.size[rx] += self.size[ry]
    self.max_val[rx] = max(self.max_val[rx], self.max_val[ry])   # 同步附加信息
    self.count -= 1
    return True

注意附加信息只在根节点上维护——非根节点的 size / max_val 是"过期"的，查的时候要先 find 到根再读。

复杂度速查

面试官常追问的几个方向

下面这些是大厂电面 / onsite 里围绕并查集常见的 follow-up，每一项后面给个最短可写的应对方向：

加权并查集（LC 399 除法求值）：除了 parent 还维护 weight[x] 表示 x 到其根节点的"边权积"。find(x) 路径压缩时把 weight 一路乘下来；union(a, b, ratio) 时按 ratio 平移挂接树。应对：模板从 parent[x] = x 升级为 parent[x] = x; weight[x] = 1.0，find 改成"路径压缩 + weight 累乘"两步。

def find(x):
    if parent[x] != x:
        root = find(parent[x])
        weight[x] *= weight[parent[x]]   # 累积到根
        parent[x] = root
    return parent[x]

可撤销并查集（在线/回滚场景）：用栈记录每次 union 修改了哪些位置 (idx, old_parent_or_size)，撤销时倒序 pop 回写。关键限制：不能用路径压缩（撤销不回去），所以单次操作降到 O(log n) 摊还（只按秩合并）。这一组合在离线分治 + 时间维度回退（如 LC 1102 / 动态图连通性）里非常常用。

离线 + 排序（LC 1697 路径权重阈值查）：把所有边按权值排序，把所有查询按阈值排序，双指针扫一遍，到当前阈值就把所有 ≤ 阈值的边 union 进去，然后回答此时刻的 connected。整体 O((n + q) log)。比在线建 MST + LCA 简单。

与 LCA / 离线分治的关系：Tarjan 离线 LCA 算法本质就是"DFS + 并查集"——回溯时把子树 union 到父节点，碰到查询 (u, v) 就读 find(v) 拿到 LCA。同样的 trick 在 Kruskal MST 里也是底层数据结构。

容易翻车的几个点：

• size[] / count 只在根节点上有效——非根节点的 size 是"过期值"，读之前必须先 find 到根
• 路径压缩之后某个节点的 parent[] 可能跳过中间节点直接到根，所以不要假设 parent[x] 是 x 的直接父亲
• 多类节点（如二分图判定）建议开 2n / 3n 节点显式表达"敌对/同类"关系，比维护 rank/color 字段省心
• 持久化/分布式场景：parent 数组不能简单 dump 到磁盘，因为路径压缩后跨进程一致性靠不住——要回到"不压缩 + 持久化树结构"或者改用 link-cut tree

7. 小结

并查集本质就是"用 parent 数组维护等价类"。掌握三件事就能套大部分连通性题：

• 两个操作：find 沿父指针到根、union 合并两个根。
• 两个优化：路径压缩（find 时把链上节点直接挂根）+ 按秩 / 按大小合并（小树挂大树）。两者同用，单次操作摊还 O(α(n))。
• 建模思维：节点可以是数字、字母、网格坐标、行列下标、字符串映射后的整数；约束可以是边、等式、同行同列。能转成"两类东西必须同组"的题都能并查集化。

什么时候不选并查集：

• 要返回具体路径（用 BFS / Dijkstra）。
• 要支持删边（除非用可撤销并查集，复杂度退化）。
• 只问"一次"连通性、边都给好（DFS / BFS 同阶且代码更短）。

下一节进入 字典树（Trie），把"字符串前缀查询"也用类似的"树形 + 数组"的思路压成 O(L) 单次操作。

对应灵神题单：常用数据结构 · 并查集

进一步阅读：灵茶山艾府《并查集题单》；LeetCode Union Find 标签 高频题