并查集从原理到实战：路径压缩、按秩合并与动态连通性全解析

并查集这个东西，在很多人的印象里是个“学了就忘、忘了再学”的尴尬存在——代码明明不到二十行，但每次真要写的时候还是会纠结：路径压缩到底怎么压？按秩合并是比大小还是比深度？更关键的是，遇到实际问题时，怎么判断“这题能用并查集”？前阵子我在做一个社交关系聚类的小项目，需要反复判断两个用户是否属于同一个可达圈子，数据量到了百万级别，才真正体会到这个高阶数据结构能有多能打。

这篇文章我打算把并查集讲透。不是简单贴一个模板让你背，而是从它解决的问题出发，把为什么要用数组、为什么要路径压缩、为什么要按秩合并、复杂度为什么近似常数、实战中能怎么用、踩过哪些坑，一层层拆开讲。不管你是刚开始接触高级数据结构的新手，还是已经背熟了模板但不太会用的人，这篇内容应该都能给你一些新东西。

1. 并查集到底在解决什么问题：一类“动态连通性”需求

1.1 一个直觉例子：社交网络里的“圈子”

先设想一个场景。你有 n 个用户，一开始谁也不认识谁。每次给你一条信息说“用户 a 和用户 b 成为了好友”，好友关系是可以传递的——也就是说，如果 a 认识 b，b 认识 c，那么 a 和 c 在某种意义上处于同一个“圈子”里。现在你需要随时回答：用户 x 和用户 y 是不是在同一个圈子里？

这就是典型的动态连通性问题。注意“动态”两个字，意味着关系是不断增加的，而不是一开始就给你一张完整的图。如果图是静态的，你可以先用 DFS 或 BFS 预处理出连通分量，之后每次查询 O(1) 回答。但关系不断新增，你不可能每次加一条边就全图重扫一遍，那就需要一种能“边加边查”的结构。

并查集就是为这种需求量身定做的。它不关心两个用户之间的具体路径是什么样，只关心“最终能不能连通”。好比你在一个陌生的城市问路，你只需要知道某个区域能不能通过步行到达另一个区域，而不需要知道每一步具体走哪条街。

1.2 两个核心操作：合并与查询

并查集（Disjoint Set Union，简称 DSU，也有叫 Union-Find 的）只支持两类操作：

• find(x)：找到 x 所在的集合代表元素，也就是集合的“根”。
• union(x, y)：把 x 和 y 所在的两个集合合并成一个。

名字里的 Disjoint 点出了一个重要性质：任意时刻，每个元素只属于一个集合，集合之间互不相交。所以并查集维护的是一组“不相交集合”的合并与归属查询。

回到社交网络的例子，union(a, b)对应“a 和 b 成为好友”，find(x) == find(y)对应“x 和 y 在同一个圈子里”。就这么简单。

这里有一个新手很容易忽略的点：并查集的查找对象是“元素”，而不是“关系”。每个元素一开始是自己所在集合的根，随着不断合并，越来越多的元素被“挂”到同一个根下面。集合的形态是一棵多叉树，根就是集合的标识。

1.3 如何判断一个需求是否适合用并查集

我在实际项目里判断一个问题能不能用并查集，一般看三个特征：

1. 只关心归属，不关心路径。如果问题明确要求输出两个节点之间的具体路径，并查集做不了，那是 DFS/BFS 或者最短路的事。
2. 操作只有“合并”和“查询”两类。注意，并查集天然不支持“拆分集合”。如果问题里有分离操作，普通并查集直接不行，得考虑可撤销版本或者其他结构。
3. 能离线处理。有些看似需要删除的操作，如果允许先把所有删除处理完再反向加回去，并查集仍然能胜任。这个技巧在后面实战部分会详细讲。

把握住这三条，比背一百道题都管用。很多所谓的“并查集难题”，本质上都是在问：你怎么把题目中的操作转化成合并和查询。

2. 从零手写并查集：从朴素实现到两大优化

2.1 用数组表达“森林”：parent 指针的意义

并查集的底层结构极其简单，一个一维数组就够了：

int parent[N];

parent[i]表示元素 i 的父节点是谁。如果parent[i] == i，说明 i 是自己所在集合的根节点。一开始每个元素都是独立的集合，所以初始化的代码是：

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

这整个结构就是一个森林——每个集合是一棵树，根是集合的代表。不理解为什么用树的人，通常会卡在“集合怎么用树表示”这个问题上。换个角度想：一个集合里总得有个“话事人”当作标识吧？树形结构的好处是，只要不断沿着父指针往上找，最终一定会到达根，这个根就是集合标识。

用树形结构表示集合，看起来多此一举——直接用集合编号不行吗？不行，因为你不知道预先会有多少个集合，也不知道哪些集合会被合并。树形结构让合并操作变成了简单的改指针，这才是精髓。

2.2 朴素实现：find 与 unite 的写法

先写一个最朴素的版本，虽然慢，但逻辑最清晰：

// 查找 x 所属集合的根 int find(int x) { while (parent[x] != x) { x = parent[x]; } return x; } // 合并 x 和 y 所在的集合 void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { parent[rootX] = rootY; // 把 x 的根挂到 y 的根下面 } }

注意unite这个名字，很多人写成union，但union在 C++ 里是关键字，所以竞赛代码里一般用unite或者merge。

朴素的 find 在最坏情况下会退化到什么程度？如果每次合并都是把一个很深的树根挂到另一个根下面，比如依次unite(1,2)、unite(2,3)、unite(3,4)……不加任何优化的话，树会变成一条链。这时find(1)需要一路走到链尾，复杂度 O(n)。当有 n 次这样的查询时，总复杂度 O(n²)，数据量稍微一大就爆了。

2.3 路径压缩：把树“拍扁”的关键一步

既然 find 的瓶颈在于链太长，那就想办法让树变矮。路径压缩的思路很直接：当我在找 x 的根时，一路上经过的所有节点，它们的根其实都是同一个。那不如直接把这条路径上所有节点的父指针都改成根节点。

递归写法非常经典，简洁到让人怀疑是不是写错了：

int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; }

这行parent[x] = find(parent[x])做的事就是：先递归找到根，然后把 x 直接挂在根下面。整个递归回溯过程中，路径上每个节点都会被挂到根上，树被“拍扁”了。

迭代版本稍微绕一点，但避免了递归开销：

int find(int x) { int root = x; while (parent[root] != root) { root = parent[root]; } // 第二遍循环做路径压缩 while (parent[x] != x) { int next = parent[x]; parent[x] = root; x = next; } return root; }

第一次循环找到根，第二次循环把路径上的节点全部指向根。思路和递归版一模一样，只是顺序不同。

这里要留意一个很多人忽略的细节：路径压缩并不会让树高立刻变成 1，它只压缩“查询过”的路径。现在把一棵树的叶子查了一次，叶子直接挂到根上，但其他分支的深度没变。真正让整体树高保持稳定的，是另一个优化——按秩合并。

2.4 按秩合并：从源头控制树的高度

按秩合并（Union by Rank）的核心思想：合并两棵树时，总是把矮的树挂到高的树下面，避免树高无脑增长。

这里的“秩”（rank），通常指树的高度（上界）。为了维护这个信息，需要开一个rank数组，初始都是 0，表示只有一个节点的树高度为 0。

int parent[N]; int rank_[N]; // 注意，rank 在 C++ 里和 std::rank 有冲突，很多人用 rank_ void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; // 矮树挂到高树下面 if (rank_[rootX] < rank_[rootY]) { parent[rootX] = rootY; } else if (rank_[rootX] > rank_[rootY]) { parent[rootY] = rootX; } else { // 两棵树高度相同，随便选一个做根，根的高度 +1 parent[rootY] = rootX; rank_[rootX]++; } }

两棵高度相同的树合并，无论谁挂到谁下面，新的树高度都会比原来多 1，所以需要给新根的秩加 1。如果高度不同，矮的挂到高的下面，总高度不变，秩自然也不用变。

这里有个误区：加了路径压缩之后，rank 数组就不再等于真实的树高了，它只是一个“上界”。但这没关系，按秩合并不需要精确的树高，它只需要一个足够好的“相对高度”来指导合并方向。你甚至可以按集合大小合并，效果同样不错：

int size_[N]; // 记录集合大小 void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; if (size_[rootX] < size_[rootY]) swap(rootX, rootY); parent[rootY] = rootX; size_[rootX] += size_[rootY]; }

按大小合并的好处是顺带维护了集合元素个数，后面要统计连通块大小时特别好用。

2.5 完整代码与初始化要点

把上面的内容整合成一个可以直接抄的模板：

class DSU { private: vector<int> parent, rank_; public: DSU(int n) { parent.resize(n); rank_.resize(n, 0); for (int i = 0; i < n; i++) parent[i] = i; } int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; if (rank_[rootX] < rank_[rootY]) { parent[rootX] = rootY; } else if (rank_[rootX] > rank_[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank_[rootX]++; } } bool connected(int x, int y) { return find(x) == find(y); } };

初始化时一定要把 parent[i] 设置成 i，这一步漏了后面全乱套。我之前见过一个项目里有人忘了初始化，直接调 find，结果每个元素都指向 0，所有查询都返回 true，排查了半天才发现是初始化问题。

3. 复杂度背后的真相：为什么两个优化缺一不可

3.1 四种实现方式的复杂度对比

很多资料直接给出结论：路径压缩 + 按秩合并后，单次操作的均摊复杂度是 O(α(n))，α 是反阿克曼函数，增长极其缓慢，在现实数据规模下可以认为是常数。

但如果你只用其中一个优化呢？

只做路径压缩而不按秩合并且在某些特殊操作序列下仍然能达到 O(log n) 的均摊复杂度，但理解起来比较费劲。普通工程场景下，两个优化一起写没有任何坏处，代码量也就多三四行，所以我从来都是两个一起写。

3.2 α(n) 是什么：一个几乎不增长的“常数”

α(n) 是阿克曼函数的反函数。阿克曼函数本身增长快得离谱，A(4, 2) 已经是一个天文数字级的数了。反函数的意思就是：α(n) 要达到一个较大的值，n 得大到难以想象。

举个例子，α(10^80) 大概是 4——你把整个宇宙中的原子总数作为 n，α(n) 也才是个位数。所以在实际工程中，把并查集单次操作当成 O(1) 没有任何问题。

但这里要强调一个容易被误解的点：O(α(n)) 是“均摊复杂度”，不是“单次最坏复杂度”。极端情况下，某一次 find 操作仍然可能要遍历很多节点，只不过这一系列操作的总代价是被控制住了。

3.3 路径压缩与按秩合并为什么是互补的

我刚开始学的时候一直没想明白：既然路径压缩能把树拍扁，按秩合并还有必要吗？

答案是：路径压缩的“拍扁”是被动的，它只在查询路径上的节点时生效。如果一个集合里有多棵子树，你只压缩了查询经过的那一条路径，其他子树的深度并没有变。如果后续频繁查询的不是刚才那条路径，那些深节点依然很深。

按秩合并则是在“源头”上做了控制：每次合并都尽量把矮树挂到高树下，让整棵树的高度增长尽可能慢。它的作用不是立刻把树拍扁，而是防止树长得太歪。

一个是事后补救，一个是源头预防，两者结合才让复杂度达到令人发指的 O(α(n))。

这里还有一个工程上的小细节：因为按秩合并已经保证了树高是 O(log n)，所以即使某些极端情况下路径压缩来不及生效，find 的最坏复杂度也只是 O(log n)，不会退化到 O(n)。这也是我为什么强烈建议两个优化一起写的原因——你得到的不仅是理论最优，还有更稳定的实际表现。

4. 经典实战应用：从最小生成树到离线倒序

4.1 Kruskal 算法：判断成环的核心工具

Kruskal 是最小生成树（MST）的经典算法，它和并查集的配合堪称天作之合。算法的流程相信大家都熟悉：

1. 把所有边按权重从小到大排序。
2. 依次取出边 (u, v)。
3. 如果 u 和 v 不在同一个集合里，就选这条边，并合并 u 和 v 的集合。
4. 如果已经在同一个集合，说明这条边会形成环，跳过。
5. 重复直到选出 n-1 条边。

如果不加最后的并查集判断，你怎么知道某条边会不会形成环？如果已经选了一些边，再选 (u, v)，只要 u 和 v 已经连通，就一定会形成环。这里“判断两个点是否连通”就是并查集的看家本领。

struct Edge { int u, v, w; bool operator<(const Edge& other) const { return w < other.w; } }; int kruskal(int n, vector<Edge>& edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int total = 0; int cnt = 0; for (auto& e : edges) { if (!dsu.connected(e.u, e.v)) { dsu.unite(e.u, e.v); total += e.w; cnt++; if (cnt == n - 1) break; } } return total; }

时间复杂度 O(m log m)，主要瓶颈在排序上，并查集部分接近 O(1)。如果不用并查集，用 BFS 每次判断连通性，复杂度直接多一个因子 O(m)，在大图上根本跑不动。

4.2 二维网格连通块统计

LeetCode 上有一类题叫“岛屿数量”：给一个二维网格，1 表示陆地，0 表示水，问有多少个连通的岛屿。

常规解法是 BFS/DFS，每遇到一个未访问的 1 就做一次搜索。但用并查集同样能做，思路是把二维坐标映射成一维索引：

int id(int i, int j, int m) { return i * m + j; }

遍历每个格子，如果是陆地，就检查它的右边和下面的格子，如果也是陆地，就合并这两个格子所在集合。最后统计有多少个陆地格子的 root 是它自己，就是岛屿数量。

int numIslands(vector<vector<char>>& grid) { if (grid.empty()) return 0; int n = grid.size(), m = grid[0].size(); DSU dsu(n * m); int dx[] = {1, 0}; // 只查右边和下面，避免重复合并 int dy[] = {0, 1}; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == '0') continue; for (int k = 0; k < 2; k++) { int ni = i + dx[k], nj = j + dy[k]; if (ni < n && nj < m && grid[ni][nj] == '1') { dsu.unite(id(i, j, m), id(ni, nj, m)); } } } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == '1' && dsu.find(id(i, j, m)) == id(i, j, m)) { ans++; } } } return ans; }

这种问题的转化核心是“把二维问题压成一维”，很多网格类并查集题目都是这个套路。相比 BFS，并查集的好处是当你还在不断动态加陆地时，它能边加边维护。

4.3 离线倒序处理：把“删边”变成“加边”

这是并查集最经典的进阶技巧，也是我认为它真正区别于其他数据结构的地方。

假设现在有一个无向图，依次执行 q 次操作，每次是“删除一条边”或者“询问两个点是否连通”。如果你顺着做，每次删边后都要重新维护连通性，而并查集不支持删边，直接卡住。

但如果你倒过来看呢？最后的图就是所有删除操作都执行完后的状态，然后从最后一个操作往前面处理：

• 最后一个操作如果是“删边”，反过来就是“加边”——这正好是并查集的强项。
• 最后一个操作如果是“询问”，直接 find 回答即可。

这个思想叫“离线倒序”，核心是改变处理顺序以匹配数据结构的能力。理解它有个关键前提：必须先知道所有操作序列，不能边输入边处理。

我记得有一次做一个项目需求，用户会动态关闭服务器之间的连接通道，同时需要随时确认两个服务当前是否还能通信。一开始顺着做怎么也做不顺，后来想到离线倒序，把流程调了个头，代码量直接砍半。这种“把删除操作积攒起来，反过来当作插入”的思路，在并查集题目里出现频率极高。

4.4 带权并查集：从连通性到“关系维护”

普通并查集只回答“是否在一个集合”，但有些问题要求知道“集合内元素之间的关系”。这就需要带权并查集：在维护父子关系的同时，维护每个节点到父节点的某种“权值”。

经典题目是“食物链”（POJ 1182）：动物分为三类，A 吃 B，B 吃 C，C 吃 A。现在给你若干条件，描述两个动物是同类还是捕食关系，需要判断哪些条件是矛盾的。

解法是用并查集维护每只动物和根节点的关系，用weight[x]表示 x 与 parent[x] 的关系，0 表示同类，1 表示 x 吃 parent[x]，2 表示 parent[x] 吃 x。

带权并查集的 find 需要同步更新权值：

int find(int x) { if (parent[x] == x) return x; int px = parent[x]; int root = find(px); weight[x] = (weight[x] + weight[px]) % 3; parent[x] = root; return root; }

注意这里必须先保存px = parent[x]，再递归，然后用weight[px]来更新weight[x]。递归回来后parent[x]已经被改成根了，如果这时候再去访问parent[x]的旧值就会出错。这是带权并查集最容易写错的地方，我在这里栽过不止一次。

合并时同样要确定权值的方向，公式经过推导可以得到：如果 x 对 y 的关系是 d（d=0 同类，d=1 表示 x 吃 y），合并 find(x) 到 find(y) 时：

weight[rootX] = (d + weight[y] - weight[x] + 3) % 3;

这个公式别死记，每次写的时候推导一遍更稳妥：假设 rootX 和 rootY 分别为两个集合的根，目标是让 x 到 rootY 的权值和 y 到 rootY 的权值满足给定关系。从 x 出发，经过 weight[x] 到 rootX，再经过 weight[rootX] 到 rootY，总权值应该等于 d 加权值 y 到 rootY 的路径补全。多画几张图就能理解。

带权并查集的价值在于：你能在维护连通性的同时，维护集合内部元素之间的代数关系（距离、差值、相对顺序等）。我后来处理“银河英雄传说”那道题时，需要维护每个战舰到队首的距离，用的就是同一个套路，只是权值从模 3 关系变成了实际距离累加。

5. 手写实现时的常见坑与排查经验

5.1 find 的递归写法：小心栈溢出

路径压缩的递归写法虽然简洁，但在极端情况下有栈溢出风险。当树高达到数万甚至数十万时，递归深度会超过默认栈限制，程序直接崩溃。

我在一个百万级节点的并查集上测过：如果只按秩合并而不做路径压缩，树高上限是 log n 级别的，递归没问题。但如果某些地方写错了，树退化成链，递归深度就是节点数，栈不爆才怪。

如果你在项目里担心这点，用迭代版 find 更安全：

int find(int x) { int root = x; while (parent[root] != root) root = parent[root]; while (parent[x] != x) { int next = parent[x]; parent[x] = root; x = next; } return root; }

这个版本没有任何递归，性能稳定，推荐在工程代码里使用。竞赛里用递归写是因为代码短、看起来优雅，但真要长期维护，迭代版是更稳妥的选择。

5.2 合并方向：swap 调用的效果

写 unite 时，最简单的写法是：

if (rank_[rootX] < rank_[rootY]) { parent[rootX] = rootY; } else { parent[rootY] = rootX; }

相当于默认让 rootX 作为新根，除非 rootX 的秩比 rootY 小。但如果换一种思路，先做 swap 再统一处理，代码会更清晰：

if (rank_[rootX] < rank_[rootY]) swap(rootX, rootY); parent[rootY] = rootX; if (rank_[rootX] == rank_[rootY]) rank_[rootX]++;

swap 之后，rootX 一定是秩较大的那一个，后续逻辑统一处理即可，不容易漏分支。两段代码等价，但 swap 版本我私心推荐，因为少了 else 分支嵌套，降低了写错的可能。

5.3 初始化顺序与“孤岛”问题

并查集最常见的隐性 bug 就是初始化遗漏。比如你只初始化了部分节点，后面的节点 parent[i] 是垃圾值，find 会指向任意内存，导致查询结果完全随机。

另一个容易忽略的问题是“孤立节点”。如果你的数据中有节点自始至终没有参与任何合并，它的 parent 始终等于自己，find 返回它自己，这是正确的。但如果你在写代码时假设“所有节点最终都合并到同一个集合”，那统计结果就会出问题。

所以写并查集时，我习惯在构造完对象后立刻把所有 parent[i] 初始化好，并且写一个测试用例专门验证“没有合并过的节点表现正常”。

5.4 带权并查集的方向约定：我踩过的坑

带权并查集最难的不是 find 的更新，而是合并时的方向约定。我踩过的坑是：合并两个集合时，把 rootX 和 rootY 的顺序搞反，导致所有后续关系全部偏置。

调试这类问题，最有效的方法是小规模数据逐步模拟：构造 3-4 个节点，手动合并几次，每一步都打印出每个节点的 parent 和 weight，看看数据的相对关系是否符合预期。不要在大数据上瞎试，那只会浪费时间。

还有一个经验是：给 weight 数组初始化为 0 一定要做，因为 0 通常表示“与自身同类”的默认关系。如果忘记初始化，后续取模运算得到的结果毫无意义。

6. 进阶变体：可撤销并查集与维护额外信息

6.1 可撤销并查集：支持回滚的版本

普通并查集不支持“撤销最后一次合并”。但在一些搜索算法和离线问题里，你需要在 DFS 回溯时恢复到之前的状态，这时候就需要可撤销并查集。

实现思路并不复杂：因为每次合并实际上只修改了两个数组元素（parent 和 rank），只要把修改前的值记录到一个栈里，回滚时弹栈还原即可。

但这里有一个关键要求：可撤销并查集不能用路径压缩。原因很直接：路径压缩会修改路径上很多节点的 parent 指针，万一要回滚，栈里得存一整个路径的信息，复杂度就失控了。所以可撤销版本只保留按秩合并，这样单次合并只改了常数个位置，回滚成本是 O(1)。

struct Change { int pos; int oldVal; }; vector<Change> history; void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { history.push_back({-1, -1}); // 空操作标记 return; } if (rank_[rootX] < rank_[rootY]) swap(rootX, rootY); history.push_back({rootY, parent[rootY]}); parent[rootY] = rootX; if (rank_[rootX] == rank_[rootY]) { history.push_back({rootX, rank_[rootX]}); rank_[rootX]++; } } void rollback() { Change c = history.back(); history.pop_back(); if (c.pos != -1) parent[c.pos] = c.oldVal; if (!history.empty()) { c = history.back(); history.pop_back(); if (c.pos != -1) rank_[c.pos] = c.oldVal; } }

这个变体在“动态图问题”里特别有用：比如判断一个图是否是二分图的某个动态版本，处理到一半要回退，用可撤销并查集就能高效维护。

6.2 维护集合大小与附加信息

有时候不仅要知道两个元素是否同集合，还要知道某个集合里有多少元素。按大小合并天然支持这个：

size_[rootX] += size_[rootY];

除了大小，你还可以在根节点上维护任何你关心的集合级信息，比如集合的总和、最大最小值。合并时只需要把两个根的信息合并：

sum[rootX] += sum[rootY]; maxVal[rootX] = max(maxVal[rootX], maxVal[rootY]);

这相当于把并查集变成了一个简易的“集合信息维护器”。我在处理一些图聚类时，会用并查集维护聚类大小和中心点坐标的累加和，最后统一算平均值，逻辑非常简单。

6.3 什么时候不该用并查集

讲到这里，我想多分享一些我自己的体会。并查集虽然强大，但它的能力边界也很明确。

• 需要动态删边时，如果问题在线（不能预知后续操作），并查集做不了，得上 LCT（Link-Cut Tree）这类更重的结构。
• 需要输出具体连通路径时，并查集只告诉你“通不通”，不告诉你“怎么通”，此时维护图结构或做搜索才是正确的。
• 需要维护集合内部顺序关系时，并查集只适用于等价关系（自反、对称、传递），如果你要维护的是偏序关系，它无能为力。
• 需要合并的规模不平衡时，比如每次合并前要检查大量不同集合之间的条件关系，并查集虽然能快速合并，但你仍然需要其他数据结构辅助枚举和筛选。

所以在实际工程和刷题中，我习惯先问三个问题：操作是合并还是删除？查询是判连通还是求路径？数据范围允不允许离线？这些问题想清楚，再动手写代码，基本不会走弯路。

并查集最让我欣赏的一点是：它把“群体归属”这种看似抽象的概念，变成了几个指针操作。几十行代码，复杂度接近常数，却能在百万甚至千万级的动态场景下稳定工作。有时候复杂的业务问题，抽丝剥茧后底层就是一个并查集——这也是我为什么一直建议每个做算法和做工程的开发者，都花心思把这个结构吃透的原因。