写并查集先从一个很常见的场景说起。你写代码的时候经常要判断两个节点在不在同一个集合里或者要把两个集合合并起来——比如无向图判连通、朋友圈划分、Kruskal最小生成树、离线处理删边问题……这些都能用并查集几行代码搞定。而且它思路简单、代码量小、效率又高几乎是我能想到的“性价比最高”的数据结构。标题里“D006【模板】”这种编号在OJ和训练集里非常常见意思就是这道题只考并查集的裸模板不掺其他复杂条件。但正因为它是模板大家反而容易掉进“背代码”的坑里。我见过不少人把find和union背得滚瓜烂熟结果一换到带权并查集、按秩合并的变形题就懵了。所以这篇博客不打算只给你一份能过题的模板而是把模板背后的设计逻辑、每个优化是干什么的、哪些地方容易写错全部拆开讲清楚。适合谁来读呢两类人。一类是刚入门算法、正在刷模板题、想知道并查集为什么这么写的初学者另一类是已经会写基本并查集但对带权并查集、复杂度分析、各种不起眼的坑还不太有把握的进阶选手。我后面会把工程上的封装写法也一并给出来做项目或者写模块想复用的时候可以直接拿过来改。1. 并查集的设计思路三句话讲清一个数据结构1.1 从“朋友圈”到 parent 数组并查集的英文叫 Disjoint Set Union简称 DSU解决的问题只有两个查两个元素是否属于同一集合把两个集合合并成一个。听起来很简单但它的精妙之处在于用一种极其省空间的树形结构做到了这一点。你想象一个朋友圈每个人只记住“我的上级是谁”最上面有一个群主群主的上司就是自己。parent[x]存的就是 x 的上级。要判断两个人是不是一个圈子的就沿着上级一路往上找看最终走到的是不是同一个群主。这个“最终走到的人”就是集合的代表元或者叫根。为什么不用数组直接存“每个人属于哪个集合”因为合并操作会变得很慢。比如集合 A 有一万人集合 B 有一万人合并时要改一万个人的归属标记。而用parent数组的树形结构合并只需要把一棵树的根挂到另一棵树的根下面改动一个节点就够了。这是并查集能在接近常数时间内完成操作的根本原因。需要注意这里的树和二叉树那种“左孩子右孩子”没关系它就是普通的森林每个节点最多只有一个父节点子节点可以有任意多个。写代码的时候parent[i] i表示 i 是一棵树的根这个初始化习惯要刻在脑子里。1.2 两种优化路径压缩与按秩合并只有parent数组的并查集最坏情况下可能退化成一条链。比如你把 1 合并到 22 合并到 33 合并到 4……最后find(1)要走 n 步才能找到根复杂度变成 O(n)。所以模板里必须有两个优化缺一不可。第一个是路径压缩。在find的过程中把沿途经过的所有节点直接挂到根下面parent[x] find(parent[x])。这样下一次再查 x一步就到根。这个优化是“懒”的只有你查过的节点才会被压缩但效果立竿见影。第二个是按秩合并。秩可以简单理解为树的高度或者一个粗略的“体重”。合并时把矮树挂到高树下面避免树越来越高。如果你只有路径压缩没有按秩合并大多数情况下也够快但个别数据会卡你如果你只有按秩合并没有路径压缩树的深度是 O(log n) 的也还行但配合起来才是公认的标准模板。我在实际竞赛里一般两个都用因为写起来也就多几行没必要赌出题人会不会卡。1.3 复杂度为什么接近 O(1)把路径压缩和按秩合并都加上之后单次操作的时间复杂度是反阿克曼函数记作 O(α(n))。这个函数的增长极其缓慢n 取整个宇宙的原子数量α(n) 也不超过 5。所以在实际应用中你完全可以把并查集的每次操作当成 O(1) 来理解。有一个很有意思的细节是路径压缩单独用摊还复杂度是 O(log n)按秩合并单独用是 O(log n)两个一配合就降到了反阿克曼函数。这也解释了为什么模板会把两个优化叠在一起——不是锦上添花而是数学上真正能把复杂度压到极致的关键组合。如果你在面试里被问到并查集复杂度不要只回答“很快”或者“差不多 O(1)”把 α(n) 反阿克曼函数这个概念说出来面试官通常就明白你是真理解了。2. 模板代码拆解从数组版到封装版2.1 最小可用模板init / find / union 三件套先给一份最标准的数组版模板这也是绝大多数 OJ 模板题的标准写法#include bits/stdc.h using namespace std; const int MAXN 100005; int parent[MAXN]; int rnk[MAXN]; void init(int n) { for (int i 0; i n; i) { parent[i] i; rnk[i] 0; } } int find(int x) { if (parent[x] x) return x; return parent[x] find(parent[x]); } void unite(int x, int y) { int rx find(x); int ry find(y); if (rx ry) return; if (rnk[rx] rnk[ry]) swap(rx, ry); parent[ry] rx; if (rnk[rx] rnk[ry]) rnk[rx]; } bool same(int x, int y) { return find(x) find(y); }init负责初始化让每个元素自成一个集合。find是路径压缩的核心。unite先找根如果已经在同一个集合就直接返回否则把矮树挂到高树上。same是查询接口。这个模板的命名比较讲究rnk而不是rank是因为在某些编译环境下rank是 C 标准库里的保留名字用了可能编译报错或者冲突省一个字母能省很多麻烦。2.2 find 的递归写法与迭代写法递归写法最简洁一行就完成了路径压缩int find(int x) { return parent[x] x ? x : (parent[x] find(parent[x])); }但递归有个隐患如果数据量很大树很深即使有路径压缩第一次查询时递归层数可能很深C 默认栈空间可能不够出现爆栈。虽然并查集经过优化后树的深度很小大部分情况下递归没问题但我在 OJ 上确实遇到过极端数据递归版find直接 Runtime Error 的情况。迭代写法更稳int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; } while (x ! root) { int next parent[x]; parent[x] root; x next; } return root; }两个循环先找根再反向把路径上每个节点都挂到根上。代码比递归长但没有任何栈溢出风险。我个人的建议是比赛里用递归版图省事做工程或者数据规模不确定时用迭代版图稳妥。2.3 封装成结构体或类的实用模板数组版写题目够用但要拿到项目里复用最好封装成一个类。下面是我常用的版本class DSU { public: DSU(int n) { parent.resize(n); rnk.resize(n, 0); iota(parent.begin(), parent.end(), 0); } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (rnk[rx] rnk[ry]) { parent[rx] ry; } else { parent[ry] rx; if (rnk[rx] rnk[ry]) { rnk[rx]; } } } bool same(int x, int y) { return find(x) find(y); } int count() { int cnt 0; for (size_t i 0; i parent.size(); i) { if (parent[i] i) cnt; } return cnt; } private: vectorint parent; vectorint rnk; };注意构造函数的iota(parent.begin(), parent.end(), 0)一行就把parent[i] i初始化完了比 for 循环干净。封装类的好处是析构自动释放内存、大小动态可变、方便加统计信息。比如count()方法可以实时返回当前有几个连通块这在很多图论题里非常实用。2.4 模板题的输入输出注意点很多刷题新手主函数写不好不是并查集的问题而是输入输出出了问题。模板题的数据量通常不小建议加上这两行ios::sync_with_stdio(false); cin.tie(nullptr);不加的话cin和cout默认要跟 C 标准 IO 同步会慢很多。再一个输出千万别用 endl用\n。endl不仅要换行还会强制刷新缓冲区在大数据下能把你从 1 秒卡到 2 秒甚至更多。主函数里的操作判断我习惯用op变量题目说 1 是合并、2 是查询就按题目来但不管怎么定核心逻辑都是两句话if (op 1) { unite(x, y); } else { cout (same(x, y) ? Y : N) \n; }模板题只要find、unite、same写对主循环几乎不会翻车。3. 并查集的经典应用套路3.1 无向图连通性与集合计数并查集最直接的应用就是判无向图的连通性。给 n 个点 m 条边边依次加进来每加一条就更新一次集合关系最后数根节点的个数就能知道图被分成了几个连通块。用count()方法统计根节点数量时有一点要注意parent[i] i在路径压缩后基本准确但如果某些节点还没被find过它可能不是直接的根。稳妥的做法是每次都调用find(i)把 i 先压缩一遍再判断。比如unordered_setint roots; for (int i 0; i n; i) { roots.insert(find(i)); } cout roots.size() \n;我个人做连通性题的时候有个习惯初始化时把并查集开成n个元素点在坐标轴上从 0 开始编号。如果题目给的是 1 到 n我会习惯性在读取时把编号减 1或者在init时把范围设成n 1从 1 到 n 初始化。两种都行但一个程序里必须统一否则越界和误判会让你排查半天。3.2 Kruskal 最小生成树Kruskal 算法是并查集在经典算法中最著名的一次出场。思路简单到不行把所有边按权值从小到大排序然后一条条尝试加入如果这条边的两个端点不在同一个集合里就把它选进生成树并合并两个端点所在集合如果已经在同一个集合里选了会成环直接跳过。这里并查集的角色就是“判环”和“合并”。每次判断same(u, v)为 false 就unite(u, v)并累加边权。当选中边的数量达到 n-1 时最小生成树就建完了。用并查集写 Kruskal 最大的好处是不用处理复杂图结构不用存邻接表一个边数组就搞定struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; vectorEdge edges; sort(edges.begin(), edges.end()); DSU dsu(n); int ans 0, cnt 0; for (auto e : edges) { if (!dsu.same(e.u, e.v)) { dsu.unite(e.u, e.v); ans e.w; cnt; if (cnt n - 1) break; } }如果所有边遍历完cnt还不到n - 1说明图不连通没有最小生成树。这个判断别漏但很多人会漏。3.3 删边问题的离线倒序处理有些题目要求你支持删边操作但并查集本质上是只加不删的。正着做很麻烦但如果你把整个操作序列读进来从后往前处理删边就变成了加边完美契合并查集的能力范围。这类题通常叫“倒序并查集”在工程里很少见但在算法竞赛里几乎是必考套路。核心步骤是先把所有要删的边标记出来。用没被删的边建初始并查集。从最后一个操作往前处理。如果是查询直接回答当前连通性如果是删除某条边反而执行unite把它加回去。这里有一个实操细节存边的时候要给每条边一个编号用编号来判断它是否被删除。如果用端点判断万一图里有重边就会出错。因为题目可能删的是“第 i 条输入的边”而不是“连接 u 和 v 的边”这两个在存在重边时是完全不同的概念。3.4 按集合维护额外信息并查集不仅能维护连通性还能在根节点上挂集合的额外信息比如集合大小、集合内权值和、最大值等。最常用的就是“维护集合大小”。如果只维护大小其实不用额外的size数组可以直接用负数的parent表示法parent[x]为负数时绝对值表示集合大小x 是根为正数时表示父节点。这样初始化时parent[i] -1合并时只需要parent[ry] parent[rx]就能更新集合大小。但如果你想要更复杂的统计比如集合内所有节点的权值和通常做法是维护一个sum[root]在unite时把两个根的sum合并。这是带额外信息的并查集常见写法。比如动态维护中间值、维护最值时需要你在合并时重新计算根上的信息。这个技巧在多校联赛题里出现的频率很高建议提前储备。4. 从裸模板到带权并查集4.1 带权并查集要解决什么问题普通并查集只能告诉你“a 和 b 是否在同一个集合”但带权并查集还能告诉你“a 和 b 之间有什么关系”。比如题目给定一系列条件x 比 y 重 3 斤a 和 b 是同类u 是 v 的祖先深度差为 2这类关系通常是有向的、可加减的你需要维护一个权值数组dist[x]表示 x 到其根节点之间的关系值。之后任意两个节点之间的关系都可以通过它们到根的关系间接算出来。拿“x 比 y 重 3 斤”举例如果 x 的根和 y 的根是同一个说明这两个量有可比性就能直接算差值如果不是同一个根说明它们之间从没建立过关系不能推算。这就是带权并查集的核心应用场景。模板题的裸并查集碰上这种题就不再是“模板”了但核心的find和unite框架还是一样的只是在里面多了权值的传递和计算。4.2 路径压缩时的权值更新带权并查集里find不仅要压缩路径还要保证压缩后dist[x]语义正确。假设dist[x]表示 x 到parent[x]的权值路径压缩后parent[x]变成根那dist[x]就要变成 x 到根的权值。递归写法int find(int x) { if (parent[x] x) return x; int p parent[x]; int root find(p); dist[x] dist[p]; parent[x] root; return root; }注意这里的顺序先递归找根再更新dist[x]。因为递归返回后dist[p]已经被更新成“p 到根”的权值了这时候再让dist[x] dist[p]算出的才是“x 经 p 到根”的总权值。容易犯的错是把parent[x] find(parent[x])写在前面然后再更新dist[x]。这样的话parent[x]已经变成了根dist[parent[x]]取到的是根到自身的值通常是 0结果就错了。我在教别人的时候喜欢让他们把这个顺序背下来先存旧父节点再递归最后更新权值。顺序错了权值一定错。4.3 合并时的权值推导合并两个集合时要计算新挂上去的根应该带多少权值。这里是最容易绕晕的地方但推导一遍就好了。假设x到y的关系值是w即关系式val(x) - val(y) w或者你定义成其它方向定下来后一路保持一致。我们有dist[x]表示 x 到rx的关系值dist[y]表示 y 到ry的关系值如果要把rx挂到ry下面设dist[rx]表示 rx 到 ry 的关系值那么关系式val(x) - val(y) w展开成路径(val(x) - val(rx)) (val(rx) - val(ry)) (val(ry) - val(y)) w前一项是dist[x]中间是dist[rx]最后是-dist[y]。于是dist[x] dist[rx] - dist[y] w所以dist[rx] w - dist[x] dist[y]; parent[rx] ry;这是最常用的写法根在两棵树之间合并方向确定的情况下非常好用。如果加了按秩合并需要根据秩决定是把rx挂到ry还是反过来方向不同dist的公式也不同推导方式一样要注意别把符号搞反。4.4 模运算与种类并查集带权并查集有一个特别著名的应用种类并查集。最经典的题目是“食物链”三种生物 A 吃 B、B 吃 C、C 吃 A。这时关系值定义成模 3 意义下的偏移量0 表示同类1 表示吃2 表示被吃。权值不是直接的加减而是在模 MOD 下运算。合并公式变成dist[rx] (w - dist[x] dist[y] MOD) % MOD;加一个 MOD 再取模是为了避免负数。如果数据范围很大可能要多加几个 MOD 再取模保证中间运算结果不会溢出。所有关系运算都在模 3 下进行每次find更新后的dist[x]要% MOD判断关系时也要通过模下的差值来判断。这类题如果不能一次 AC大概率就是取模没取干净或者方向定义不一致。我的建议是写之前先在草稿纸上写下“dist[x] 表示 x 相对根的关系且吃为 1、被吃为 2”然后全程照着这个定义推导不要中途改口。5. 常见问题与排查技巧实录5.1 递归爆栈怎么办即使有路径压缩在某些特殊构造下第一次递归深度仍可能很深。我在一次练习赛中就遇到过数据给了 10^6 个点操作全是把当前点连到前一个节点然后查询最后一个点和第一个点的关系。递归版find直接在深递归时崩溃。解决方案就是改成迭代版find上一章给过的双循环写法。或者如果环境允许可以在程序开头手动扩栈比如 C 里加#pragma comment(linker, /STACK:102400000,102400000)再或者用setrlimit提高栈空间。但这些手段不如直接换迭代版干净毕竟迭代版没有环境依赖。5.2 初始化遗漏与负数下标新手常见第一位的问题忘了调用init(n)。parent数组默认全是 0如果不初始化所有元素都指向 0整个并查集就是错的。查这个问题的方法很简单——每条测试用例的第一行输出打印一下parent[0]和parent[1]看看是不是0和1瞬间就暴露了。第二个容易踩的坑是数组下标。题目如果从 1 开始编号而你的init从 0 到n-1那么访问parent[n]就界了。解决方法是init(n 1)或者读取时--x; --y;。我个人更倾向于init(n 1)这样思路比较直不用每次读入都想着减一。5.3 带权并查集的更新顺序错误带权并查集最常见的问题不是公式推错而是find里更新顺序出错。上一章强调过先存父节点再递归后更新权值。如果写成int find(int x) { if (parent[x] x) return x; parent[x] find(parent[x]); dist[x] dist[parent[x]]; return parent[x]; }看起来只差一行顺序但结果完全不对。因为递归前parent[x]还没变成根递归后parent[x]变成根了dist[parent[x]]是根到根的权值通常初始化成 0你少加了一段中间权值。排查这种问题时不要光看逻辑直接打印一棵小树的所有dist值和手算对比。比如构造三个点设 dist[1]3、dist[2]5然后find(1)看看结果对不对。手算一次就全明白了。5.4 只做路径压缩够不够很多人为了省代码只写路径压缩不写按秩合并。确实大多数题目都能过但有两个隐患一是理论复杂度从反阿克曼函数退化成 O(log n)虽然实际上也很小但在刻意构造的数据下还是会慢。二是有些平台的并发环境或特殊评测方式会对递归深度敏感没有按秩合并会让树更深。我个人写模板题时会把按秩合并加上反正就是if (rnk[rx] rnk[ry]) swap(rx, ry);两行的事。而且一旦你接受了带权并查集的写法按秩合并和权值推导可以一起封装并不会多花多少脑力。如果实在嫌麻烦说明你刷的题还没有到需要在意复杂度的程度等碰到 TLE 了再回来加也不迟。5.5 并查集题目常见报错速查表症状可能原因排查方法Runtime Error数组越界检查下标从 1 开始还是从 0 开始Runtime Error递归爆栈改用迭代版 findWrong Answer忘记初始化确保 main 开头调用 init(n)Wrong Answerparent 和 rnk 命名冲突用 rnk 代替 rankWrong Answerfind 更新顺序错误对照 4.2 节顺序检查Time Limit Exceeded没关同步流加 ios::sync_with_stdio(false)Time Limit Exceeded输出用了 endl换成 \n输出全错但逻辑正确编号从 1 开始数组只开了 ninit(n 1)这张表我每次带新人刷题前都会发给他们基本上能覆盖九成并查集题目的低级错误。我自己刷题多了之后看报错类型就能猜出问题出在哪一环节效率提升非常明显。6. 一些用过才知道的小习惯做并查集几年下来我自己养成了一些谈不上专业但很实用的习惯最后分享几个给你。第一任何代码动parent之前先确认这是不是根。很多人写着写着就忘了parent[x]可能不是根直接用parent[x]去比较两个集合结果在路径压缩不完整的时候出 bug。安全做法是永远通过find拿到根再操作。第二封装成类之后same和unite里都要先find再操作不要在调用方再 find 一遍。接口保持纯粹调用方只需要知道“并查集自己能处理好一切”这样代码更简洁也更好复用。第三多准备一个count方法的封装类。图论题里统计连通块数量太常用了没有count方法你每次都要遍历一遍数组代码冗余还容易漏。加一个这个方法很多题目直接省一段循环。如果你最近在刷模板题不妨把这篇博客里的代码存成自己的模板文件。以后遇到并查集相关题目直接复制再根据题目改一下dist的定义和合并公式基本上不会卡。模板这东西关键不在于背而在于你知道每一行为什么这么写。理解了底层那点逻辑之后不管题目换成带权、种类还是离线倒序你都能借同一套思路拆掉它。