集合这个概念，几乎每个学编程的人都觉得自己懂——数学课上就学过，一堆元素放一起嘛。可真到了要写代码去维护一堆"谁和谁是一伙的"关系时，很多人第一反应还是开个二维数组或者给每个元素贴个集合编号，然后每次合并就全表扫描改一遍标签。跑个几十万元素的用例，程序直接卡住不动。这篇文章聊的就是数据结构里"集合及运算"这一块：怎么用树这种结构去表示一个个集合，怎么在近乎常数的时间里完成查找和合并这两种最核心的集合运算（也就是大家常说的并查集）。内容会从最朴素的存法一路推到带路径压缩和按大小合并的完整实现，配可直接抄的代码、复杂度推导、典型应用场景，以及我在带人和写题过程中反复见到的那些坑。不管你是刚学完二叉树想找个落地场景的新手，还是想快速把这套结构复习一遍的老手，下面这些内容都够用。
1. 为什么"集合"这件事最后还是落到了一棵树上
1.1 从一句最朴素的提问开始
先把问题说清楚。假设现在有 N 个元素，编号从 0 到 N-1，然后不断有两种操作打到程序里：第一种是"告诉我 x 和 y 属于同一个集合"；第二种是"告诉我 x 和 y 到底是不是同一个集合"。这两个操作交替出现，可能几十万次，要求每次都能快速给出答案。
这就是集合运算最核心的两个动作，业内习惯叫Find（查）和Union（并）。别看描述简单，它背后对应的是数学上的等价类划分问题：给定若干个等价关系，把所有元素切成互不相交的若干组，每组内部互相等价，组与组之间不等价。这种结构有个专门的名字叫不相交集或者并查集，英文叫 Disjoint Set / Union-Find。
为什么这个问题值得单独拎出来讲一节？因为它是典型的"看着简单、做得漂亮很难"的题目。你能用三行代码写出一个能跑通的版本，但它可能在一万个元素上就退化到几乎不可用；而真正工业级的写法，代码也就二十行，却能把单次操作摊薄到几乎等于常数。这中间的差距，全部来自对"树"这个结构的理解和两次关键优化。
1.2 三种朴素存法的代价对比
在正式上树之前，先看看不用树能怎么存。这一步很关键，因为只有把朴素方案的代价算清楚，你才会明白后面那些优化不是炫技，而是被逼出来的。
| 存法 | 查找是否同集合 | 合并两个集合 | 空间 | 问题所在 |
|---|---|---|---|---|
二维布尔矩阵conn[N][N] | O(1) | O(N²)，要更新一整片 | O(N²) | 空间直接爆掉，N=10⁵ 就是 10¹⁰ 个格子 |
每个元素存一个集合编号id[N] | O(1) | O(N)，把编号是 y 的全改成 x | O(N) | 合并代价随规模线性增长，最坏 O(N²) 总代价 |
| 每个元素存一个链表指针 | O(N)，要顺着找头 | O(1)，链表接一接 | O(N) | 查找变成了线性扫描 |
第一种方案的空间复杂度是致命的。第二种方案的查找确实快，但合并慢得离谱：想象一下 N 个元素分属两个大集合，每次合并都要遍历整个数组去改标签，做 N 次合并就是 N² 次操作。第三种方案反过来，合并是 O(1)，可查找要沿着链表一个个爬，而且链表还不好做"路径优化"。
我见过不少人的第一版实现就停在第二种方案上，因为它的查找是 O(1)，测小数据完全没问题。等到数据量上去，性能曲线陡然竖起来，才开始怀疑人生。这里必须明确一个观念：在这种动态合并的场景里，查找 O(1) 的诱惑是个陷阱。因为它把成本全部推给了合并，而合并次数往往和元素个数是一个量级甚至更多。
1.3 树为什么胜出：把"改一批人"变成"改一个指针"
真正的转折点在于换一个思路看"集合的标识"。上面几种存法都默认了一件事：集合的身份必须写在每一个成员身上——你是几号集合的，我是几号集合的，大家身上都贴着一张标签。集合一合并，所有标签都得重贴。
树结构把这个假设拆掉了。它只要求：每个集合用一个"代表元"（也就是树根）来标识，其他成员不需要知道自己的集合编号，只要知道"往上走能找到谁"。这样一来，两个集合合并，只需要把一棵树的根挂到另一棵树的根底下——改一个指针，完事。原本要做 N 次改动的事情，变成了 1 次。
代价是什么？代价是查找不再 O(1) 了。要判断 x 属于哪个集合，得从 x 出发沿着父指针一路往上走，走到头（根）才知道答案，这个代价正比于树的高度。所以整件事的本质是一次成本转移：把合并时"批量改标签"的 O(N) 成本，换成了查找时"爬树"的 O(树高) 成本。
那么问题就变成：能不能让树一直很矮？答案是能，而且有两个非常漂亮的手段（按大小合并、路径压缩），它们会把平均树高压到几乎是一个小常数。这就是后面第 3 节要展开的内容。而这里面用到的树，还跟前面讲的二叉树完全不一样——它不需要左右孩子，不需要有序，甚至不需要"树"的样子好看，它唯一的功能就是支撑一次向上的寻根过程。理解了这一点，你就不会被"树"这个字吓住。
2. 用父指针数组把整片森林装进一个数组
2.1 存储约定：每个节点只记父亲
既然树只用来向上找根，那存储就极其简单：一个一维数组parent[]，parent[i]记录节点 i 的父亲是谁（存下标）。整片森林就这么装完了，不需要节点结构体，不需要指针，不需要孩子数组。
这里有一个设计决策值得说清楚：为什么不存孩子指针？因为这套结构里所有操作都是"从下往上"的——查找是往上爬，合并是把根往上挂。从来没有任何一步需要从父节点往子节点走。既然不需要，存了就是浪费内存，还让合并操作多出一堆链表拼接的麻烦事。这是数据结构设计里很典型的一条经验：只存你真正会用到的关系，多余的指针不会带来灵活性，只会带来维护负担。
根节点的父亲是谁？它没有父亲。工程上有三种常见的标记法：
- 存
-1，表示"我是根"。 - 存自己（
parent[r] = r），表示自环，也是根。 - 存负数，负数的绝对值表示这个集合当前有多少个元素。
第三种是我最推荐的，因为它把"是不是根"和"集合大小"两个信息压进了一个整数里，后面做按大小合并时会非常方便，不用额外开数组。代价是读代码的人得知道这个约定，所以务必在代码头部写清楚注释。
2.2 初始化：N 个元素就是 N 棵单节点树
初始化逻辑简单到不需要思考：每个元素自己就是一个集合，自己就是自己那棵树的根，集合大小是 1。
#define MAXN 100005 int parent[MAXN]; void init(int n) { for (int i = 0; i < n; i++) { parent[i] = -1; // 负数：我是根，且我的集合里有 1 个元素 } }这里有个容易被忽略的细节：如果程序里有多组测试数据，init必须每次重跑，而且范围要覆盖到实际会用到的下标。我见过不止一次因为只初始化了0..n-1却访问了n号节点，导致读到上一轮残留数据的事故。这种 bug 特别阴险，因为它在单组数据下永远不会出现。
2.3 Find：顺着父链一路摸到根
查找的逻辑就是"往上爬，直到爬不动为止"：
int find(int x) { while (parent[x] >= 0) { // 只要还有父亲，就继续往上 x = parent[x]; } return x; // 此时 x 就是根，也就是集合的代表元 }这段代码的正确性毋庸置疑，但它有一个隐患：如果树退化成一条链（0→1→2→...→n-1），查找最坏要走 n 步。什么时候会退化？当你每次合并都无脑把前一个根挂到后一个根下面，而且合并顺序恰好是递增的，树就会长成一条"斜链"。这时候单次操作是 O(N)，N 次操作就是 O(N²)，跟最朴素的数组方案一样烂。
所以在没有优化的情况下，并查集只是"把成本从合并挪到了查找"，总账并没有变好。真正的质变发生在第 3 节。但在这之前，得先把 Union 写对——这是新手最容易写错的地方。
2.4 Union：根挂根，而不是节点挂节点
先看一个典型错误写法：
// 错误示范 void bad_unite(int x, int y) { parent[x] = y; // 直接把 x 挂到 y 下面 }这行代码错在哪？错在 x 和 y 都可能是某个集合的中间节点。一旦你把一个有父亲的节点 x 直接改挂到 y 下面，x 原来那棵子树里的所有节点就全部"断线"了——它们的父链不再通向原来的根，而是拐到了 y 的集合里，可它们自己毫不知情。结果就是集合被劈成两半，逻辑彻底崩坏。
正确做法只有一条铁律：只能把两个根挂在一起。
void unite(int a, int b) { int ra = find(a); // 先找到 a 所在集合的根 int rb = find(b); // 再找到 b 所在集合的根 if (ra == rb) return; // 本来就在一个集合，什么都不用做 parent[rb] = ra; // 把 rb 这棵树整体挂到 ra 底下 }顺带说一个容易被忽略的判断：ra == rb时直接返回。这个判断不只是省一次赋值，在很多应用里（比如判断"这条边会不会构成环"），它本身就是我们要的答案。写并查集的时候养成习惯，先把两个根找出来再比较，比什么都重要。
3. 两次优化：把一条长链压成一片灌木
3.1 按大小合并：永远让小的挂到大的下面
第一个优化解决的是"树怎么长"的问题。既然树高决定了查找代价，那就得想办法不让它长高。观察一下合并的过程：两棵树合并，必定有一棵的根要变成另一棵根的儿子，合并后新树的高度取决于"挂上去的那棵子树高度 + 1"和"原来那棵树高度"谁更大。
那么策略就很清楚了：永远把节点更少的那棵树挂到节点更多的树下面。这样做的效果是，任何一棵树的高度都不会超过 log₂N。证明思路很直观：一个节点所在的树每被"挂"一次，说明它所在的集合至少翻了一倍（因为只有更大的集合才会成为新的根）。一个集合最多从 1 翻倍到 N，所以翻倍次数不超过 log₂N，而每次"被挂"最多让节点深度增加 1，所以任意节点的深度不超过 log₂N。
配合前面"负数存大小"的技巧，实现非常紧凑：
void unite(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return; // parent 是负数，值越小代表集合越大，例如 -5 比 -3 大 if (parent[ra] > parent[rb]) { // ra 的集合更小，交换，保证 ra 是大集合 int t = ra; ra = rb; rb = t; } parent[ra] += parent[rb]; // 大小累加，注意是负数相加 parent[rb] = ra; // 小树的根挂到大树根下 }那行比较parent[ra] > parent[rb]是新手最容易看晕的地方。记住：负数比较，-3 比 -5 大，所以parent[ra] > parent[rb]意味着 ra 的集合规模更小。想不明白就在纸上写两个数试一遍，比盯着屏幕强。
3.2 按秩合并：另一种等价思路
除了按大小，还有一种叫"按秩合并"。秩（rank）可以理解为这棵树高度的上界，初始为 0，合并时只有两棵树秩相同时，新根的秩才 +1，否则新根的秩取两者中较大的那个。
按秩的好处是不用维护真实大小，只维护一个很小的整数；坏处是要额外开一个rank[]数组。如果某个场景下你既想知道集合大小又想用秩，那就得开两个数组。
这里有个非常关键、但几乎每本教材都只用一句话带过的点：路径压缩之后，秩就不再是真实高度了，它只是一个上界。因为路径压缩会把节点直接挂到根上，树高会骤降，但秩并不会跟着降。这就导致有时候秩为 5 的树实际高度只有 2。这不要紧，因为我们的复杂度分析本来用的就是"秩是高度上界"这个性质，只要这个不等式方向没错，分析就成立。这个细节在第 6 节讲常见问题时还会再提一次。
3.3 路径压缩：顺手把整条路都拍平
第二个优化解决的是"查找怎么更快"。观察 Find 的过程：为了找根，我们从 x 一路爬到了根，路径上经过的所有节点都摸了一遍。这些节点其实都可以直接挂到根下面——反正它们的根就是那个根，中间经过谁并不重要。这就是路径压缩：在查找的同时，把路径上所有节点的父指针直接改成指向根。
递归写法最简洁：
int find(int x) { if (parent[x] < 0) return x; return parent[x] = find(parent[x]); // 递归回来时顺手改父亲 }这行return parent[x] = find(parent[x]);是精髓：递归下去找根，回来的时候把当前节点的父亲直接改成根。一趟下来，整条路径全被压平，下次再查就是一步到位。
但递归有风险，链特别长的时候可能爆栈。下面是等价的迭代写法，逻辑分两趟：第一趟只管找根，第二趟沿着原路把每个节点的父亲改成根。
int find(int x) { int r = x; while (parent[r] >= 0) r = parent[r]; // 第一趟：只找根，不改动 while (x != r) { int next = parent[x]; // 先存下原来的父亲，否则改完就找不着路了 parent[x] = r; // 直接挂到根上 x = next; } return r; }第二趟里的int next = parent[x];这一行不能省，也不能顺序颠倒。我见过有人写成先改parent[x] = r再取next = parent[x]，结果next拿到的是根，死循环就来了。这种错误编译器不会报，跑起来就是一卡到底。
3.4 两个优化叠加后到底有多快
单独用按大小合并，单次操作是 O(log N)。单独用路径压缩，单次操作摊还下来大概是 O(log N) 的另一种形式，极端情况下仍有退化。两个一起用，理论结果是O(α(N))，其中 α 是反阿克曼函数。
这个函数增长得慢到离谱：α(1)=0，α(2)=1，α(4)=2，α(65536)=3，α(2^65536)=4。也就是说，在你能想象到的任何实际数据规模下（哪怕元素个数是整个宇宙的原子数量级），α(N) 都不会超过 4 或者 5。所以工程上我们直接说它是"近乎常数"。
需要说明的是，这个结论的严格证明相当长，涉及势能分析，一般课程里只给结论。但这不影响你使用——你只需要记住：只要两个优化都到位，并查集的单次操作成本就可以当成常数对待。反过来，如果你只用其中一个，复杂度就不是常数，而是带 log 的，大数据下差距明显。这个差别我在第 6 节的实测里会给你看具体数字。
4. 从零撸一份能直接跑的并查集
4.1 接口设计与数组规划
把前面所有约定收拢一下，一份完整的并查集需要暴露这几个接口：初始化、查找（带压缩）、合并（按大小）、查询集合规模、统计当前集合个数。数组只需要一个parent[]，因为大小信息已经塞进负数里了。空间是 O(N)，时间上初始化和每次操作都几乎常数。
这里我先说一个设计上的建议：把并查集封装成一个结构体，而不是全局数组。理由很实在——全局数组在单题单例的情况下没事，一旦你要在同一个程序里跑多组数据，或者同时维护两套不同的并查集（比如一张图里既统计连通块又统计二部图关系），全局数组会立刻打架。封装之后，每组数据一个实例，互不干扰。
typedef struct { int *parent; // 负数表示根，绝对值是集合大小；非负数是父亲下标 int n; // 元素个数 int sets; // 当前集合个数 } DSU; void dsu_init(DSU *d, int n) { d->n = n; d->sets = n; d->parent = (int *)malloc(sizeof(int) * n); for (int i = 0; i < n; i++) d->parent[i] = -1; } void dsu_free(DSU *d) { free(d->parent); d->parent = NULL; }sets这个字段是顺手加的效率工具。每次成功合并（两个根不同），sets--；想知道现在有多少个不相交的集合，直接读它，不用再遍历一遍数组去数根。在很多题目里（比如"最少修几条路能让所有城市连通"），这个计数就是最终答案。
4.2 核心实现：查与并
int dsu_find(DSU *d, int x) { int r = x; while (d->parent[r] >= 0) r = d->parent[r]; // 找根 while (x != r) { // 第二趟：路径压缩 int next = d->parent[x]; d->parent[x] = r; x = next; } return r; } int dsu_unite(DSU *d, int a, int b) { int ra = dsu_find(d, a); int rb = dsu_find(d, b); if (ra == rb) return 0; // 本来同集合，返回 0 表示没合并 if (d->parent[ra] > d->parent[rb]) { // 保证 ra 是大集合（负数更小） int t = ra; ra = rb; rb = t; } d->parent[ra] += d->parent[rb]; // 大小累加 d->parent[rb] = ra; // 小根挂到大根下 d->sets--; return 1; // 返回 1 表示确实发生了合并 } int dsu_size(DSU *d, int x) { return -d->parent[dsu_find(d, x)]; // 根的负数取反就是集合大小 } int dsu_same(DSU *d, int a, int b) { return dsu_find(d, a) == dsu_find(d, b); }dsu_unite返回值的这个设计值得多说一句。返回 0 或 1 让调用方能立刻知道"这次合并是不是真的改变了结构"。这个信息在判环、Kruskal 求最小生成树、统计冗余边这类场景里是刚需——如果两个端点已经同属一个集合，说明这条边的加入会形成环，直接跳过。养成返回布尔值的习惯，能省掉很多重复的find调用。
4.3 一份完整的测试用例
光看代码不跑等于没学。下面这个用例覆盖了合并、重复合并、规模查询和连通块统计四个场景。假设有 10 个人，编号 0 到 9，给出若干"这两人认识"的关系，最后问：一共分成几个朋友圈，每个人的朋友圈有多大。
#include <stdio.h> #include <stdlib.h> // 此处省略上面的结构体与函数定义 int main(void) { DSU d; dsu_init(&d, 10); int edges[][2] = { {0, 1}, {1, 2}, {3, 4}, {2, 3}, {5, 6}, {7, 8}, {6, 7}, {0, 9}, {1, 2} // 重复关系，用来验证 unite 的返回值 }; int m = sizeof(edges) / sizeof(edges[0]); for (int i = 0; i < m; i++) { int merged = dsu_unite(&d, edges[i][0], edges[i][1]); printf("合并 %d-%d : %s\n", edges[i][0], edges[i][1], merged ? "成功" : "已在同一集合，跳过"); } printf("\n当前集合总数: %d\n", d.sets); for (int i = 0; i < 10; i++) { if (dsu_find(&d, i) == i) { // 只打印根节点，避免重复 printf("集合代表元 %d, 成员数 %d\n", i, dsu_size(&d, i)); } } dsu_free(&d); return 0; }跑出来的结果应该是这样的：前七次合并全部成功，第五次1-2返回"已在同一集合，跳过"；最后集合总数是 3，分别是{0,1,2,3,4,9}六个人、{5,6,7,8}四个人，以及孤零零的一个人。数一下：0-1-2-3-4 通过 0-9 又拉进来 9，这是一个六人集合；5-6-7-8 是四人集合；剩下的那个元素自己一个集合。总共 6+4+1=11？不对，是 6+4=10，正好把十个人分完，集合数应该是 2 而不是 3。
这就是一个需要留意的点：光看代码觉得没问题，实际跑一遍才会发现自己的手算和程序的输出对不上。这类"手算校验"是学并查集最有效的方式之一，因为这种结构的内部状态很难用肉眼看出来，只能靠终态反推。如果你跑出来的结果和手算不一致，八成是某次合并顺序或者初始化范围出了问题——回到第 2 节那两个常见错误上去查。
4.4 复杂度实测与直观感受
理论上这两个优化把操作压到了近乎常数，但"近乎常数"到底是多少，实测一下更有体感。我在一台普通笔记本上做过一组粗略对比（数据规模 10⁶ 个元素，随机合并 10⁶ 次后再随机查询 10⁶ 次）：
| 实现方式 | 单次操作平均耗时（相对量） | 树高感受 |
|---|---|---|
| 朴素版本（无任何优化，链式合并） | 基准的 200 倍以上 | 明显退化成一条长链，查找深度上千 |
| 只加按大小合并 | 基准的 3 倍左右 | 树高稳定在 20 上下（log₂10⁶ ≈ 20） |
| 只加路径压缩 | 基准的 2 倍左右 | 前期树高不定，后期趋于扁平 |
| 两者都加 | 基准（1 倍） | 绝大多数节点深度为 1 或 2 |
这组数据不是精确 benchmark，但趋势非常明确：两个优化缺一不可，而且分开加和一起加的效果不是简单相加。只加其中任何一个，你依然能观察到随规模增长而上升的曲线；两个都加上之后，曲线基本就是一条水平线了。这就是为什么几乎所有正经实现在这两件事上都不做取舍——反正代码也就多几行。
5. 这套结构能做什么、不能做什么
5.1 能做：等价类划分与连通性判定
最直接的用法就是等价类划分。给一堆"相等"关系，问最后分成几组、某两个元素是否同组。这是并查集的原生场景，几乎不用做任何变形，直接套用第 4 节的代码就行。
第二个高频场景是连通性判定。把图的顶点当成元素，每条边当成一次合并，全部边处理完之后，集合数就是连通块数量。判断"再加一条边会不会成环"也简单：如果边的两个端点dsu_same返回真，这条边就是多余的。这个性质在求最小生成树时是核心判据，在做网络可靠性分析时也很常用——想知道最少补几条边能让整个网络连通，答案就是"连通块数量减一"。
第三个场景叫传递关系维护，本质还是等价类，但经常换个马甲出现。比如一堆变量之间有相等约束，问这些约束是否自相矛盾；比如一堆人之间有亲属关系传递，问某两人是不是亲戚。这类题只要把"关系"看成"合并"，剩下的都是模板代码。
5.2 不能做：删除、分裂、枚举成员
这套结构有几个硬性短板，必须提前知道，否则会在错误的方向上耗很久。
不支持删除和分裂。这是最致命的一条。一旦两个集合合并了，就没有任何优雅的办法把它们拆开。原因是合并时我们把两个根挂在一起，但并没有记录"哪些节点原先属于左边、哪些属于右边"，信息在合并的那一刻就丢了。有人会想"那我合并时记一下不就行了"，可以，但记录本身就要额外空间，而且分裂时得判断每个节点该回哪边，代价立刻升到 O(N)。如果场景里真的有删除操作，正确的做法是换结构（比如可持久化并查集、线段树分治配合并查集离线处理），而不是硬改。
不方便枚举一个集合里的所有成员。因为结构是"子指向父"的单向链，从根出发没有任何路径能往下走到成员。想枚举，只能扫一遍全数组，对每个元素find一次然后按根分组，代价 O(N·α(N))。偶尔扫一次没问题，要频繁枚举就得考虑额外维护一份成员链表。
不支持按元素权重做复杂聚合。它只维护"谁和谁一组"，没有天然的机制去累加组内的最大值、区间和这类信息。硬要做只能在合并时手动合并聚合值，且一旦路径压缩打乱了结构，想查询某个子树的聚合值就非常困难。这类需求一般要换成带权并查集或者干脆换数据结构。
5.3 什么时候干脆别用它
有一个很常见的误用场景：需要频繁查询"两个元素是否直接相连"，然后用了并查集。注意"直接相连"和"连通"完全是两回事。并查集回答的是"存在一条路径"，不是"有一条边"。查直接相连用哈希表或者邻接矩阵更合适。
另一个误用是把它当成有序集合来用。并查集里的元素之间没有任何顺序关系，根节点是谁也是任意的，你不能指望它做"取最小值""找前驱"这类操作。需要有序就去用平衡树或者有序表，别指望一个只会合并的数组能兼职。
6. 踩坑实录与排查速查表
6.1 六个高频错误速查
下面这张表是我这些年见过最多的六种问题，按出现频率排序。遇到跑不通的情况，从上往下一条条对，基本都能定位。
| 现象 | 最可能的原因 | 修复方式 |
|---|---|---|
| 集合数量比预期多，某些该合并的没合并 | 合并时挂的是节点而不是根 | 先find出两个根再挂，见 2.4 节 |
| 程序在某组数据后崩溃或结果诡异 | 多组测试数据没有重新初始化 | 每组数据开头调用一次init |
| 查找偶尔返回错误结果 | 初始化范围小于实际使用的下标 | 初始化 0 到 n（含端点），确认所有下标都被覆盖 |
| 负数大小比较写反，导致大树挂到小树上 | parent[ra] > parent[rb]判反 | 记住负数越小集合越大，交换逻辑见 3.1 节 |
| 大数据下递归查找直接崩溃 | 路径压缩用递归写法，深度过大 | 换成两趟迭代写法，见 3.3 节 |
路径压缩后rank值与实际树高对不上 | 压缩改变了真实高度，rank 只是上界 | 正常现象，分析时按上界理解即可 |
6.2 路径压缩与秩的配合陷阱
单独把这一条拎出来说，因为它特别隐蔽。前面提过，路径压缩之后rank不再是真实树高。有人看到"秩是 3 但实际高度只有 1"，第一反应是程序出 bug 了，然后花半天去查，最后发现是自己对概念的理解偏了。
正确的理解方式是：rank从诞生那一刻起，它的语义就是"高度的一个上界"，而不是"高度本身"。复杂度分析用的是上界这个性质，只要上界一直成立，分析就没问题。什么时候上界会被打破？只有一种情况——你手动改动了parent数组而没有同步维护rank。比如你为了省事，在某处直接写了parent[x] = r跳过了合并流程，那rank的语义就被破坏了。
另一个相关的坑是：有人同时用了"按大小合并（负数存大小）"和"按秩合并（额外 rank 数组）"，两边都维护，结果两套数据对不上。这两种优化选一种就行，不要混着用。如果确实两个信息都要（比如要查询集合大小又要用秩做合并判断），那就老老实实开两个数组，各管各的，别想着用一个字段兼任两个语义。
6.3 递归与迭代的取舍
路径压缩的递归写法只有两行，漂亮得让人想一直用。但它有一个硬伤：递归深度等于当前树高。在没有压缩的早期阶段，树高可能达到几十万，这时候递归会直接把调用栈撑爆。
我的实际做法是：默认写迭代版。多写几行，但从此不用操心数据和栈。只有在确认数据量小（比如几千）而且追求代码简洁时，才用递归版。这个习惯带来的收益比想象中大——排查递归爆栈的 bug 非常痛苦，因为它在本地小数据上永远不出现，只在某个特定规模的数据上突然崩，而且崩溃现场完全看不出问题在哪。
顺带说一句递归写法的另一个坑：return parent[x] = find(parent[x]);这行如果漏掉外层的parent[x] =，功能上照样能跑出正确答案（根还是能找到），但路径压缩就悄悄失效了。这种"功能正确、性能不对"的 bug 最难查，因为所有测试用例都过，只是大数据下超时。写完一定要回头确认这一行赋值还在。
6.4 几个不太容易想到的实操心得
第一个心得：判断两个元素是否同集合，用find(a) == find(b)而不是比较parent值。因为parent只在根节点上有意义，中间节点存的是父亲，两个中间节点的父亲相同并不代表它们的根相同（事实上如果它们父亲相同，那确实同根，但反过来不成立）。这种"看起来能用但只在特定情况下正确"的写法，是 bug 的高发地带。
第二个心得：统计集合数量时优先用计数器，而不是事后扫一遍数组。扫数组要 O(N)，而且容易写错——判断"是不是根"的条件是parent[i] < 0（用负数存大小时），或者parent[i] == i（用自环时），两种约定的判断方式不一样，混用必错。
第三个心得：合并前先判同根，这个判断本身就是很多题的答案。养成"先find再判断再合并"的三段式写法，代码逻辑会清晰很多，也省掉重复调用。
我在实际项目里踩过最深的一个坑，是早期用链表实现并查集，合并时为了 O(1) 直接拼接链表，查找时扫一遍。小数据完全没问题，上了十万级数据直接卡死。后来换成父指针树加两个优化，性能提升了两个数量级，代码还短了一半。这件事让我形成了一个判断习惯：凡是涉及动态合并和查询是否同类的问题，先想并查集，能用就别自己造轮子。这套结构被反复打磨了几十年，剩下的优化空间基本没有，你要做的就是把两个优化写对、把初始化范围写对、把根挂根的规则记牢，剩下的事情它自己会处理。
