你大概率在“数据结构”相关的章节里见过它并查集英文叫 Disjoint Set Union简称 DSU。我第一次认真吃透它不是在上课而是在一场笔试里被一道“动态加边判断连通”的题恶心到之后。当时我只会DFS染色每加一条边就重扫一遍图结果数据一到 10 万级别就直接超时。后来才明白如果问题只关心“两个元素在不在同一个集合”不关心它们之间的路径长什么样并查集就是最优解之一。这篇文章适合正在学数据结构的人、准备考研或面试的人以及工作中和连通性、等价类问题打交道的工程师。我会从最笨的写法一路讲到带权并查集的偏移量公式顺带把工程里容易踩的坑也一起说了。1. 先搞清楚并查集到底在解决哪一类问题1.1 一个真实场景朋友圈的圈子假设一个社交平台有 n 个用户平台给你 m 条“互相关注”的关系问你最终有多少个互不连通的圈子。如果你用图的 DFS/BFS每次来一条新关系可能要重新遍历一次图复杂度直接裂开。而并查集的做法是初始时每个人都属于自己的集合每来一条关系就把两个人所在的集合合并最后数一下还有多少个集合。这里面最关键的一点是并查集不关心“A 和 B 是怎么连起来的”也不关心中间经过了几个人它只回答两个问题find(x)x 属于哪个集合通常返回集合的“代表元素”根。union(x, y)把 x 和 y 所在的两个集合合并成一个。查询“x 和 y 是否认识”就变成find(x) find(y)。就这么简单所有并查集的花活都建立在find和union这两个动作上。1.2 适合并查集的三个特征我在实际做题和写代码时总结出三个信号。只要问题同时满足这三条大概率可以用并查集只关心“是否连通”“是否同类”不关心具体路径。一旦要输出路径那就是图论里 BFS/DFS 或者最短路径算法的活了。操作里有大量“合并集合”。比如动态加边、把两个等价类并在一起。关系具有传递性。A 和 B 连通B 和 C 连通那 A 和 C 也一定连通同类关系、朋友关系、网络可达性都满足这条。反过来什么时候别用并查集我也列个清楚的对比表场景是否适合并查集原因判断两个点是否连通且边不断增多适合合并操作 O(α(n))几乎常数需要输出两点之间的具体路径不适合并查集会压缩路径不保留路径信息需要删除边、撤销合并不适合标准并查集不支持分裂操作需要统计每个集合内部详细分布看情况可以额外维护 size、权值和但复杂统计不行给一组相等/不等约束判断是否矛盾特别适合本质就是等价类合并问题这套“特征判断法”比背模板有用得多。我见过不少同学拿着并查集往最短路径题上套结果越套越乱就是因为没想清楚第一点。1.3 初始化的两种习惯写并查集第一步是初始化。常见有两种写法// 写法一parent[i] i根指向自己 for (int i 0; i n; i) parent[i] i; // 写法二parent[i] -1用负数表示根同时用绝对值表示集合大小 vectorint parent(n, -1);第一种写法最直观判断根就是parent[x] x。第二种写法节省一个 size 数组因为parent[root] -size但可读性差一点我自己平时用第一种笔试面试也推荐第一种不容易写错。后面所有代码都基于parent[i] i。2. 朴素实现为什么慢慢在哪儿2.1 最直觉的“打标签”写法很多人第一次接触“合并集合”第一反应是维护一个标记数组label[i]表示元素 i 属于几号集合。合并集合 A 和 B 时把 B 里所有元素的 label 改成 A 的编号。这个写法的问题一眼就能看出来合并一次需要扫描整个数组O(n) 复杂度。如果有 m 次合并最坏就是 O(nm)。数据规模一大比如 n10万、m10万直接 100 亿次操作跑题都要跑到超时。2.2 用树表示集合把慢的问题转移掉聪明一点的做法是用树结构。每个集合看成“一棵树”树根是这个集合的代表元素。parent[i]不再存集合编号而是存 i 的父节点根节点的 parent 指向自己。find(x)从 x 沿着父指针往上爬直到某个parent[root] root返回 root。union(x, y)找到 x 和 y 的根把一个根接到另一个根下面。合并两棵树只需要改一个指针O(1)查找的耗时取决于树的高度。这个设计把“合并要扫描全集合”的高昂代价转移成了“查找要走一条链”的代价。看起来很美但有一个致命问题。2.3 退化成链一次糟糕的合并顺序毁掉一切如果合并的时候不加任何策略总是把后一棵树的根接到前一棵树的根下面连续合并 1-2、2-3、3-4……树会越长越高1 ← 2 ← 3 ← 4 ← 5此时find(5)要走 4 步find(n)要走 n-1 步。合并 m 次、查询 m 次的复杂度就变成 O(n m·n)和打标签法半斤八两甚至更糟。这个退化问题是并查集所有优化的出发点。记住一句话并查集的性能瓶颈从来不是合并且本身而是查找时爬树的深度。3. 两大优化路径压缩与按秩合并3.1 路径压缩查一次就把路踩平路径压缩的思想非常朴素find(x)在从 x 爬到根的过程中把沿途所有节点的父指针直接改成根。这样下次再查这些节点一步就到根。递归写法在代码上只有一行int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); }这个写法把“找到根”和“路径上所有节点指向根”两件事一起干了。不熟悉递归的人可能看着晕但它的语义很清晰如果 x 不是根先把 x 的父节点也 find 到根然后把 x 的父指针指向根返回根。如果担心递归爆栈后面我会专门讲这个坑可以用迭代版完全压缩int find(int x) { int root x; while (parent[root] ! root) root parent[root]; while (parent[x] ! x) { int nxt parent[x]; parent[x] root; x nxt; } return root; }这两段代码维护的集合语义完全一样路径压缩只是把树压矮了并没有改变“哪些元素属于同一个集合”的事实。3.2 按秩合并永远让矮树接到高树上路径压缩能把树压得很扁但它解决不了“合并时把一颗很高的树接在另一颗更高树上”的情况。按秩合并就是给 union 加一条纪律把高度小的树根接到高度大的树根下面。秩的定义有两种常见实现一种是维护高度rank一种是维护节点数sz。我平时更愿意按集合大小合并因为 size 可以在后面统计集合大小时直接复用void unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return; if (sz[ra] sz[rb]) swap(ra, rb); parent[rb] ra; sz[ra] sz[rb]; }为什么按大小合并能保证树高因为一个节点所在树的大小每经过一次合并至少翻倍。树高超过 log n 的前提是集合大小超过 2^log n n矛盾。所以单看按秩合并能保证树高 O(log n)。3.3 两个优化加起来均摊复杂度逼近常数教科书里最经典的结论是只用路径压缩m 次操作的摊还复杂度是 O((mn) log n)只用按秩合并是 O(m log n)两个同时用复杂度是 O(m·α(n))其中 α 是反阿克曼函数。反阿克曼函数增长有多慢慢到你几乎无法直观感受即使 n 是宇宙中原子数量的级别α(n) 也不会超过 5。所以在实际工程和竞赛里你可以直接认为并查集“接近 O(1)”。我用一个表格把复杂度演变放这儿方便你复习时一眼看明白实现方式单次合并/查询最坏复杂度m 次操作摊还复杂度朴素打标签数组O(n)O(nm)树结构无优化O(n)O(nm)树 只做路径压缩O(log n) 期望O((mn) log n)树 只按秩合并O(log n)O(m log n)树 路径压缩 按秩合并O(log n) 理论最坏实际极小O(m·α(n))面试和考研如果问到“为什么并查集快”你背下这张表的最后一列就够了。但要理解背后的原因路径压缩让树越用越矮按秩合并让树从一开始就不容易长高两者是不同层面的保护。3.4 只用一个优化够不够实际写代码时只做路径压缩的并查集已经能跑得非常快很多模板干脆只写 find 不写 rank。但我的建议是两个都写上。理由有三条只做路径压缩构造数据可以把摊还复杂度卡到 O((mn) log n)虽然不算灾难但没必要赌。按秩合并保证了树的深度上界这对“可撤销并查集”“可持久化并查集”这些进阶玩法是必要的——那些场景不能用路径压缩只能靠按秩合并控制深度。维护 size 数组额外成本极低还能顺手支持查集合大小。既然零成本为什么不写4. 带权并查集从“是否同类”到“偏了多少”4.1 普通并查集只回答“是不是”带权并查集回答“差多少”普通并查集能回答“A 和 B 在不在同一个集合”但很多问题要求更多A 比 B 大 3B 和 C 颜色相同C 和 D 颜色相反……这时集合内部还要维护“相对关系”。最经典的例子里食物链算一个A 吃 BB 吃 CC 吃 A。现在给你一串“x 吃 y”“x 和 y 同类”的陈述让你判断哪些是假的。如果只用普通并查集你只知道 x 和 y 是否在同一个关系图里却不知道它们之间到底是谁吃谁。带权并查集就是干这个的。4.2 核心思想把相对关系看成模 k 的偏移假设每个元素有一个“真实值” value(x)我们不知道它具体是多少但知道它和另一个元素的差值。定义off[x]表示 x 相对根的值差off[x] value(x) - value(root(x)) (mod k)其中 k 是关系总数。比如只有“同类/异类”两种关系k2食物链三类关系k3。find(x)不再只是把父指针指向根还要同步更新 off。递归时顺序很关键int find(int x) { if (parent[x] ! x) { int p parent[x]; parent[x] find(p); off[x] (off[x] off[p]) % k; } return parent[x]; }注意必须先让 p 的父指针也指向根、p 的 off 更新为“p 到根的偏移”然后才能把 x 的旧偏移x 到 p加上 p 的新偏移p 到根。顺序一乱off 就全乱了。合并操作要解决的是已知value(x) ≡ value(y) c (mod k)如果 x 和 y 不在同一个集合怎么把两个集合并起来假设把 ry 挂到 rx 下面需要算off[ry] value(ry) - value(rx)。推导过程value(x) off[x] value(rx) value(y) off[y] value(ry) 已知 value(x) ≡ value(y) c off[x] value(rx) ≡ off[y] value(ry) c value(ry) - value(rx) ≡ off[x] - off[y] - c (mod k)所以// 设定 value(x) ≡ value(y) c (mod k) bool unite(int x, int y, int c) { c (c % k k) % k; int rx find(x), ry find(y); if (rx ry) { // 同集合验证已有关系是否满足条件 return (off[x] - off[y] - c) % k 0; } parent[ry] rx; off[ry] (off[x] - off[y] - c k) % k; return true; }这里最容易被绕晕的地方是“方向”。不同教程里 off 的定义方向可能相反有的用“根到 x 的偏移”有的用“x 到根的偏移”公式符号就会差一个负号。我的建议是自己固定一种定义比如上面这种把推导过程在纸上走一遍之后就永远用这一套不要背别人的公式。4.3 食物链模 3 的经典应用食物链题POJ 1182里的关系是循环的0 吃 11 吃 22 吃 0。如果给三类动物编号 0、1、2那么“x 吃 y”可以表达为value(x) ≡ value(y) 1 (mod 3)“x 和 y 同类”就是value(x) ≡ value(y) 0 (mod 3)。读入每句话时若是“x 和 y 同类”调用unite(x, y, 0)。若是“x 吃 y”调用unite(x, y, 1)。unite返回 false 就说明这句话和之前已知的事实矛盾是假话。难度不在并查集本身而在于把“吃”的关系翻译成差值。翻译对了代码就是模板的机械重复。4.4 另一个方向扩展域并查集带权并查集不是处理“相对关系”的唯一办法。当关系类型很少最常见的就是“相等/不等”两种可以用扩展域把每个变量拆成多个点。比如 LeetCode 990 的等式方程题变量只有 0/1 两种取值每个变量 x 拆成两个结点x 表示“x 为 0”的命题xn 表示“x 为 1”的命题。已知 x y合并 (x, y) 和 (xn, yn)。已知 x ! y合并 (x, yn) 和 (xn, y)。如果最后发现 x 和 xn 被并到了同一个集合说明“x 同时等于 0 又等于 1”矛盾。那什么时候用带权什么时候用扩展域我的经验是关系是模 k 循环/差值的用带权关系只有“同/不同”两类、并且可以拆成若干个明确命题的用扩展域。扩展域代码稍微长点但逻辑更好理解不容易把符号搞反。5. 一份能直接抄的模板以及两个经典题目复盘5.1 我自己常用的 C 模板以下是我平时做题用的普通并查集模板带路径压缩和按 size 合并class DSU { public: vectorint parent, sz; DSU(int n) : parent(n 1), sz(n 1, 1) { for (int i 0; i n; i) parent[i] i; } int find(int x) { int root x; while (parent[root] ! root) root parent[root]; while (parent[x] ! x) { int nxt parent[x]; parent[x] root; x nxt; } return root; } bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; if (sz[ra] sz[rb]) swap(ra, rb); parent[rb] ra; sz[ra] sz[rb]; return true; } };默认下标从 0 到 n-1。如果你需要从 1 开始编号构造时多传一个 n1 就行其他不用改。带权版本就用前面写的WeightedDSUunite(x, y, c)的语义是“设定 value(x) ≡ value(y) c (mod k)”。这套定义我用了很久推导过两次之后基本不会错。5.2 Python 的写法注意递归深度Python 写并查集有个隐藏坑默认递归深度大概只有 1000。如果数据规模大递归版 find 分分钟 RecursionError。所以 Python 版我一般写迭代完全压缩class DSU: def __init__(self, n): self.parent list(range(n)) self.size [1] * n def find(self, x): root x while self.parent[root] ! root: root self.parent[root] # 第二遍循环做完全路径压缩 while self.parent[x] ! x: nxt self.parent[x] self.parent[x] root x nxt return root def unite(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb] return TruePython 里也可以用sys.setrecursionlimit(10**6)强行放开递归限制但迭代版更稳。带权并查集在 Python 里如果必须递归我通常只在小数据上这么写或者用栈模拟递归来更新 off。5.3 题目复盘省份数量LeetCode 547这题给的矩阵isConnected[i][j] 1表示 i 和 j 直接相连让你数有多少个省份连通分量。用并查集就是无脑合并DSU dsu(n); for (int i 0; i n; i) for (int j 0; j n; j) if (isConnected[i][j]) dsu.unite(i, j); int ans 0; for (int i 0; i n; i) if (dsu.find(i) i) ans;核心技巧在最后统计根节点满足find(i) i数一下有几个根就是几个连通块。这个技巧比用 set 去重所有 find 结果更快。5.4 题目复盘等式方程的可满足性LeetCode 990这题给一堆a b和a ! b的等式问有没有可能全部满足。关键点是先把所有等号处理完再处理不等号。DSU dsu(26); // 26 个字母 for (auto e : equations) if (e[1] ) dsu.unite(e[0] - a, e[3] - a); for (auto e : equations) if (e[1] ! dsu.find(e[0] - a) dsu.find(e[3] - a)) return false; return true;为什么要分两遍因为a b和b c合并之后你才能知道a和c也必须相等如果a ! c在合并前检查它们当时可能还不在一个集合就会漏掉矛盾。做题时最容易踩的坑就是边读边判断这类题以后都记住先合并所有相等约束再验证所有不等约束。6. 工程实战中的并查集以及我踩过的坑6.1 除了刷题工程里真有用到吗很多人觉得并查集就是面试/考研题工程用不上。实际上我用过的地方包括Kruskal 最小生成树边按权值排序依次尝试加入。每次要快速判断“加这条边会不会成环”并查集一句find(u) find(v)就搞定。这是算法课之外最典型的并查集应用。图像连通区域标记把像素坐标压成一维索引像素值相同的相邻像素做 union最后统计根的数量就是连通区域个数。编译器/数据库里的等价类合并当两个变量被约束为相等时本质上就是把两个等价类合并之后传递等式的判断都是并查集操作。社交网络反作弊/社群检测的预处理把“同一个设备登录过的账号”合并成集合后续分析直接以集合为单位。套路都一样把元素映射成下标把“等价/连通”翻译成 union把“是否相同”翻译成 find。大家如果只盯着代码很容易忽略这个抽象层但工程上真正值钱的其实是这层翻译能力。6.2 坑一递归 find 在大数据下会爆栈有一次我在本地跑 10 万节点的并查集递归版 find 直接段错误。原因很简单虽然路径压缩让树很矮但如果你还没做几次查找树还很高递归调用的层级就可能达到几千甚至上万层。解决方式有两个一是改用迭代版完全压缩前面代码已经给了二是如果必须用递归版至少在主函数里把栈空间调大。我个人的原则是普通并查集一律写迭代版只有带权并查集才用递归版——因为带权 find 需要回溯父节点来更新偏移迭代版写起来繁琐且容易错。6.3 坑二下标从 0 还是 1二维坐标怎么压坐标压成一维是并查集工程化的常见需求。比如一个 m 行 n 列的网格点 (i, j) 映射成i * n j然后parent数组开m * n。下标统一从 0 开始不然你会在parent[x * n y 1]这种地方反复越界。如果你的节点不是连续整数比如是字符串 IP、账号 ID可以用一个unordered_mapstring, int做懒散列映射第一次见到某个 key 时把它分配一个新下标。这相当于动态扩容的并查集写起来也很顺手。6.4 坑三并查集没有“撤销”操作标准并查集只支持合并不支持把两个集合重新拆开。遇到“动态删边”类问题怎么办一个常用套路是离线倒序处理既然删边难那就先把所有操作读完确定最终状态然后从后往前“加边”把删边问题转化成加边问题。工程里大多数需要“删边”的场景都可以这样迂回解决。更进阶的可撤销并查集做法是不用路径压缩只用按秩合并并把每次 union 修改的父节点和 size 记录在栈上回滚时弹栈恢复。这就是为什么我前面强调“按秩合并”不只是性能优化还是可撤销玩法的基础。6.5 坑四带权并查集的取模和方向错一个全盘崩带权并查集最磨人的不是公式推导而是方向。我见过太多人背了食物链模板却不知道每行的意思换道题就死。调试经验有两个画一棵三节点的小树手动走两遍 find把 off 的更新过程写出来看和代码逻辑是否一致。写一个暴力验证程序小规模随机数据用普通数组模拟集合逐个验证和并查集结果对拍。我个人几乎所有带权并查集的题都是靠对拍过的因为手推太容易漏掉模的边界。取模千万别忘了先把负数修正成非负数((x % k) k) % k。C 的%对负数会返回负值这一步漏了后面全出问题。最后说说我自己的体会。并查集代码短看起来十几行但它是我见过的“原理和实战差距最大”的数据结构之一。你把find的路径压缩、union的按秩合并、带权版本的偏移更新这几件事真正在纸上推过一遍之后后面再学可撤销并查集、可持久化并查集、树上带权并查集会顺很多。建议大家拿到任何并查集题目先把“关系如何翻译成差值”写下来再动代码不要上来就套模板——我踩过的所有坑几乎都是因为跳过了这一步直接开写。