真题里出过无数次的并查集到底是“看着会了、一写就废”还是真的吃透了差别就在这几点上。不管你是在准备考研数据结构还是在刷力扣、AcWing上的图论题又或者已经进入工作想回头补一补基本功并查集都是那种“一辈子只需要彻底理解一次之后就能反复用”的知识点。这篇文章我会从最基础的合并查找讲起把种类并查集、带权并查集这两类进阶变体一次讲透配上可以直接抄的代码模板和我在实际刷题中踩过的坑。1. 并查集到底是什么一个“快速判联通”的思想模型1.1 从朋友圈连通问题说起先想一个生活中特别常见的场景你打开社交软件系统提示“你与某人可能认识”。背后的逻辑千千万万但有一条最朴素的链路——如果A和B是好友B和C是好友那么系统就有理由猜测A与C可能有共同圈层。这里的关键问题不是“找出所有好友关系”而是快速判断任意两个人之间是否存在一条通过好友关系串联起来的通路。用专业的说法这就是“动态连通性”问题在图中边会不断加入我们要随时回答“两个点是否连通”。你当然可以用BFS/DFS每次现搜但点一多、查询一密复杂度会高到没法看。并查集就是专门为这种场景设计的数据结构它把同一连通块里的所有点纳入一个“集合”查询两点是否连通本质就是判断它们是否属于同一个集合。“并查集”这三个字本身已经说清楚了它支持的两类操作并Union把两个集合合并成一个。查Find查找某个元素属于哪个集合通常也用它判断两个元素是否属于同一集合。加上“集”字是因为它在逻辑上确实维护着一组互不相交的集合。初始时每个点都是孤立的随着我们不断把有关联的点合并到一起这些集合逐渐变大最终形成若干个连通块。整棵结构内部通常用一棵树来组织树根就是集合的代表元素。1.2 为什么用“一棵树”来组织集合每次判断两个点是否连通最朴素的方案是给每个连通块一个“编号”然后维护每个点属于哪个编号。麻烦在于合并时如果直接把其中一个连通块里所有点的编号改成另一个连通块的编号最坏情况下需要遍历大量点。并查集的做法是每个集合选出一个代表元素根每个普通元素只记录自己的父节点是谁。查询时沿着父节点一路向上走到根如果两个元素的根是同一个那么它们在同一个集合中。合并时更简单直接把一个集合的根挂到另一个集合的根下面当成子节点树的高度最多增加1。这个设计让“合并”从O(n)变成了O(1)代价是“查找”变成跟树高相关。所以后面的优化基本都是在想方设法让树变矮这也就引出了路径压缩和按秩合并两个经典操作。2. 基础并查集手写一遍胜过看十遍2.1 三个核心接口与完整实现基础并查集虽然简单但它是所有进阶变体的地基。我把代码写在这里每个接口都附带注释这是我最开始学的时候给自己做的标注版本。#include iostream #include vector using namespace std; class DSU { private: vectorint parent; // parent[i] 表示 i 的父节点 vectorint rank; // 秩树的近似高度 public: DSU(int n) { parent.resize(n); rank.resize(n, 0); for (int i 0; i n; i) { parent[i] i; // 初始时每个点的父节点是自己即自成一派 } } // 查找 x 所在集合的根节点同时进行路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归地把路径上所有节点直接挂到根下面 } return parent[x]; } // 合并 x 和 y 所在的两个集合 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]; } } // 判断 x 和 y 是否在同一个集合中 bool same(int x, int y) { return find(x) find(y); } };这段代码看起来简单但有几个细节很多初学者会忽略。find里如果不做路径压缩那么unite里虽然只合并了根节点树还是会慢慢变长最坏会退化成一条链find的复杂度就变成O(n)。路径压缩的奥妙在于每次查找时顺手把沿途所有节点都平铺到根下面这样下次再查这些节点就只需走一步。两个优化同时用上时并查集单次操作的均摊复杂度趋近于常数级的反阿克曼函数效率极高。2.2 递归find的隐患与迭代写法上面的find用了递归代码简洁但存在一个隐藏问题当树特别深的时候递归可能导致栈溢出。这在实际刷题中并不罕见比如在极端数据构造下即便有按秩合并递归层数也可能很大。稳妥起见可以写成迭代版本int find(int x) { int r x; while (parent[r] ! r) { r parent[r]; // 先找到根 } // 第二遍循环做路径压缩 while (parent[x] ! x) { int tmp parent[x]; parent[x] r; x tmp; } return r; }这个版本需要两遍循环第一遍找根第二遍把路径上所有节点都直接挂到根下。虽然代码比递归长但完全避免了栈溢出风险。我在力扣上做大型测试数据时习惯直接用迭代版省心。2.3 顺手实现的小功能维护连通块数量很多题目除了查询连通性还会问“当前有多少个互联不连的块”比如在无向图中加边问还有几个连通分量。这时只要再维护一个计数器初始化时计数器等于点数n。每次unite真的合并了两个不同集合时计数器减1。这个写法很自然但我见不少人用遍历所有点来判断根是否重复来计算复杂度高得多。其实只需在合并时做一个简单的cnt--复杂度就是常数级。顺手还能维护每个连通块的大小合并时把size[rootX] size[rootY]对统计群体规模特别有用。3. 种类并查集当关系不止“连通”这一种3.1 食物链模型三类动物之间的捕食关系基础并查集只能处理“同类”关系两个点属于同一集合就是连通。但现实中的关系常常是“A吃BB吃CC吃A”这种有方向、有类别的。经典的食物链题目就这样有N只动物编号1到N所有动物只属于A、B、C三类。已知A吃BB吃CC吃A。给定若干条陈述有些是“X和Y是同类”有些是“X吃Y”需要判断哪句话是假的。这种题如果用基础并查集根本没法表示“X和Y不同类且还有捕食关系”。这时候就需要种类并查集也叫扩展域并查集。思路是把原来的每个点i拆成三个状态i本身表示“i是A类”i n 表示“i是B类”i 2n 表示“i是C类”。这样一来原来一维的N个点就扩展成了3N个点。任何一条关系陈述都可以用这些点之间的合并来表达。“X和Y同类”就是它们三个类别的状态分别对应合并“X吃Y”则把X、Y的类别按吃与被吃关系错位合并。3.2 合并规则怎么定越界检查为什么重要我们拿食物链题来抠细节。假设编号从0开始那么每个动物x有三个节点x表示A类xn表示B类x2n表示C类。如果要合并“X和Y是同类”那就执行unite(x, y); unite(x n, y n); unite(x 2n, y 2n);如果要合并“X吃Y”那等价于把X类与Y的下一个类别联系在一起也就是unite(x, y n); // X是A Y是B unite(x n, y 2n); // X是B Y是C unite(x 2n, y); // X是C Y是A这里最关键的检查是在合并前要先排除矛盾。比如“X和Y是同类”这句陈述如果为假就必须满足之前已经确立了“X吃Y”或“Y吃X”。判断写法是// 同类陈述合法性检查 if (same(x, y n) || same(x, y 2n)) { // 说明之前已经确定 X 和 Y 有捕食关系矛盾 } // 捕食陈述合法性检查 if (same(x, y) || same(x, y 2n)) { // 说明之前已确定同类或者 Y 吃 X矛盾 }这个“先查矛盾、再执行合并”的顺序绝对不能乱。我见过不少初学者先执行了合并再来判断结果union操作把本来不该合并的关系也合并了导致后面的判断全部失效。代码逻辑看起来只是顺序不同但结果天差地别。3.3 种类并查集的另一种套法二分图判定很多人不知道种类并查集还能用来判二分图。二分图要求所有边连接的两个节点必须分属两个不同的点集这正是“两类关系”的模型。所以用两倍空间就能判把每个点拆成“属于左集合”和“属于右集合”两个状态每条边u-v就做unite(u, vn)和unite(un, v)如果中途发现same(u, v)或者same(un, vn)图就不是二分图。这种方法比染色DFS更直观特别是处理动态加边的二分图问题并查集有天然优势。把“种类”从三类拓展到类逻辑完全一样只是空间从2n变成kn。4. 带权并查集记录数值差、偏移量的利器4.1 除了认爹还要记父子之间的距离种类并查集能处理“不同类”但如果题目要求的是“具体相差多少”比如“X比Y重3千克”或者“X在Y左边5个单位”种类并查集就无能为力了。这时要上带权并查集也叫边权并查集、加权并查集。带权并查集的核心变化是给每个节点到父节点之间挂了一个权重weight[i]。这个权重可以理解为i到parent[i]的差值、距离或偏移量。初始时每个节点自成一派parent[i] iweight[i] 0。查询根节点的路径压缩过程不再是简单地跳过父节点而是要累加路径上的所有边权int find(int x) { if (x ! parent[x]) { int origin parent[x]; // 先保存原来的父节点 parent[x] find(origin); // 递归找根并压缩 weight[x] weight[origin]; // 累加权重 } return parent[x]; }这段代码是带权并查集的灵魂。注意origin保存了递归前x的原始父节点在递归结束后origin已经被挂到了根节点下面所以weight[origin]表示的是origin到根的偏移量。此时weight[x] weight[origin]把x到根的总偏移算出来。整个过程有点像一个树上“前缀和”路径压缩时顺便把每个节点到树根的偏移量记下来。4.2 合并时权值怎么算向量法一劳永逸合并两个集合时最怕的就是权值公式写错。我建议直接把它当向量迁移问题来做。假设我们已知x到它的根rootX的偏移量为weight[x]y到它的根rootY的偏移量为weight[y]题目给出的关系是 x 到 y 的偏移量为 d即val[x] - val[y] d这里减号方向要看题目定义需保持一致。如果要把rootX挂到rootY下面构成parent[rootX] rootY那么我们需要算出rootX到rootY的偏移量。可以用一个简单的向量三角形来想先看关系val[x] - val[y] d。我们把val拆开val[x] weight[x] val[rootX]val[y] weight[y] val[rootY]所以(weight[x] val[rootX]) - (weight[y] val[rootY]) d如果我们希望让rootX成为rootY的子节点即weight[rootX]表示val[rootX] - val[rootY]那么从上式反解weight[rootX] d weight[y] - weight[x]这个结果很规律新权重等于题目给的关系值加上被合并点y的权值减去主动查数点x的权值。顺序别记反不然全错。用同样的推导方式如果是把rootY挂到rootX下面则weight[rootY] -d - weight[y] weight[x]只要理解了向量三角形合并时不管以谁为根都能快速推出正确表达式。4.3 一个通用带权模板我这里给出一份完整的带权并查集模板注释尽量写清楚class WeightedDSU { private: vectorint parent; vectorlong long weight; public: WeightedDSU(int n) : parent(n), weight(n, 0) { for (int i 0; i n; i) parent[i] i; } int find(int x) { if (x ! parent[x]) { int origin parent[x]; parent[x] find(origin); weight[x] weight[origin]; } return parent[x]; } // 建立关系value[x] - value[y] diff // 如果已经在一个集合返回是否满足已有关系 bool unite(int x, int y, long long diff) { int rootX find(x); int rootY find(y); if (rootX rootY) { return weight[x] - weight[y] diff; } // 把 rootX 挂到 rootY 下 parent[rootX] rootY; weight[rootX] diff weight[y] - weight[x]; return true; } };这个模板里的find返回值是根节点同时更新了每个节点的权重。unite的返回值代表这条关系是否与已有信息矛盾这在带权并查集题目里特别常见很多题就是不断给关系、判断真假。diff的类型建议用long long因为差值题经常出现大数运算。5. 实战中的坑这六个问题我每次都会提醒自己5.1 合并方向的优先级式子容易写反带权并查集里把rootX挂到rootY下面和把rootY挂到rootX下面公式完全不同。我一开始总记不住后来干脆不再记忆具体式子只记“向量三角形”的推导方式。做题时花10秒钟重新推一遍比在调试时花20分钟找bug划算得多。还有一点合并方向的优先级与rank相关时如果使用了按秩合并就得根据谁当根选择对应的公式不能只套一个方向的模板。5.2 取模出现负数需要专用的归一化函数种类并查集在判断x和y的类别关系时经常要计算(weight[x] - weight[y]) % k之类的表达式。C里负数取模还是负数比如-2 % 3的结果是-2直接拿去跟0、1、2比较必出错。这时候需要写一个mod函数int mod(long long a, int k) { return (a % k k) % k; }这个函数的原理是先让余数落在-k1到k-1之间再加上k把负数抬成正数后再取模结果永远落在0到k-1之间。做食物链这类题这个函数几乎是必需品。5.3 递归爆栈时把find改成迭代之前已经提到过find用递归写很简洁但遇到深度大的数据可能爆栈。带权并查集的find因为要累加权重迭代写法会稍微复杂一点但原理不变先沿着父链收集所有节点再统一更新父节点和权重。我个人习惯先写递归版本通过小样例发现爆栈再换成迭代版。绝大多数比赛环境递归栈比较宽松但力扣的某些极端用例会有风险提前做好预案更稳妥。5.4 种类并查集空间一定要开足把N个点扩展成kN个点之后最典型的问题就是数组越界或合并时下标漏加偏移量。比如食物链里三个类别的偏移量写n x、2 * n x时中途很容易把某个n漏掉。这个没法靠技巧避开只能靠反复检查。我的经验是在合并前先把三个unite调用行单独列出来逐个核对偏移量是否正确宁可多花10秒也不要让bug藏到最后。5.5 大数据量别用cin关同步也没用很多并查集题目输入量巨大动辄几万几十万行。cin即使加了ios::sync_with_stdio(false)在极端情况下仍然可能比scanf慢。遇到这种题我直接上scanf或者C的快读模板。刷题不是炫技稳定通过才是目的。考研和面试机考都有时间限制在这上面浪费几秒都可能得不偿失。5.6 出题人最爱的“离线建图并查集”场景有些题目看起来和并查集毫无关系实际上是典型的“离线处理”问题先把所有查询读进来然后按某种顺序统一处理。比如区间内最小连通、边权值由大到小加入等过程中需要用并查集维护当前状态。这类题在LeetCode周赛和AcWing题单里非常常见掌握并查集的核心思路后看到“动态连通性”“边逐渐加入”这些话术基本就可以往并查集方向想。6. 从入门到熟练我推荐的刷题顺序与模板总结6.1 按难度递进的题目清单我自己学习并查集时按照下面这个顺序刷题效果比较好分享给大家参考阶段题目来源说明基础入门洛谷 P3367 【模板】并查集最标准的基础模板先跑通最基础的合并查询基础应用LeetCode 547 省份数量维护连通块数量顺手练习计数逻辑基础应用LeetCode 684 冗余连接在加边过程中判断是否成环经典场景种类并查集洛谷 P2024 / POJ 1182 食物链三个类别的经典模型必做种类并查集Codeforces 某类“真假命题”题把区分奇偶性的问题转成两种状态带权并查集AcWing 240 食物链带权版用带权方式再做一遍加深理解带权并查集LeetCode 399 除法求值带权并查集最直观的应用之一带权并查集力扣/牛客 区间和查询系列差分约束思路和并查集结合的场景6.2 我最终常驻的模板选择模板这种东西不是越复杂越好而是越顺手越好。我现在日常工作里最常用的其实是基础版加上两种扩展的混合体struct DSU { vectorint parent, sz; vectorlong long w; DSU(int n 0) { init(n); } void init(int n) { parent.resize(n 1); sz.assign(n 1, 1); w.assign(n 1, 0); iota(parent.begin(), parent.end(), 0); } int find(int x) { if (parent[x] x) return x; int r find(parent[x]); w[x] w[parent[x]]; return parent[x] r; } // 带权合并: val[x] - val[y] d bool merge(int x, int y, long long d) { int rx find(x), ry find(y); if (rx ry) return w[x] - w[y] d; if (sz[rx] sz[ry]) { swap(x, y); swap(rx, ry); d -d; } parent[ry] rx; w[ry] w[x] - w[y] - d; sz[rx] sz[ry]; return true; } };这个模板把按大小合并和带权结合在了一起写题时直接复制改改就能用。merge里先按大小决定谁当根再根据方向统一调整d的符号。一定要记住swap之后的d -d这一步等号两边的方向要对齐不然全盘皆错。6.3 扩展场景Kruskal、动态连通性与离线回答除了上述经典题目并查集还会出现在这些场景里Kruskal最小生成树边按权值排序后依次用并查集判断两端是否已连通不连通就加上这条边并合并。这是并查集在算法竞赛中最经典的应用之一。动态连通性不断插入新边并询问两个点当前是否连通。这种问题用并查集可以非常优雅地支持在线回答。离线回答区间问题比如“按时间倒推删除边”的题目先把所有操作读入然后倒序执行把删除变成添加配合并查集处理。维护集合内其他信息可以在并查集节点上额外维护最大值、最小值、最大公约数等信息合并时同步更新。我个人在刷题时最大的体会还是那句老话并查集考的不是复杂度而是建模能力。你能把题目中的关系想成点与点之间的距离差、类别差并查集才能发挥威力。食物链模型很多人第一次看不懂但亲手写完一遍、再拿带权版本对照着写一遍之后整个思路就清晰了。之后再碰见种类并查集、带权并查集的选择题先问自己一句题目是在讨论“是同或异”还是“差多少”前者用扩展域后者用边权方向对了剩下就是模板套用了。