如果你写过图论题，一定遇到过这种尴尬：明明只需要判断“两个点是否在同一个连通块里”，用 DFS 或者 BFS 每次重新搜一遍也能做，可一旦操作量到了十万、百万级别，前面的做法就肉眼可见地变慢。这时候并查集就成了很多人的第一选择。它实现简单、思路直观，但很少有人第一次就能把路径压缩、按秩合并、带权更新这些细节全部写对。这篇文章不打算做教科书式的名词堆砌，而是从“它到底在解决什么问题”开始，一步步推到代码和习题，最后把实战里容易踩的坑也一起说清楚。适合正在学数据结构的同学、准备算法面试的开发者，以及想快速把并查集用起来的竞赛新手。
1. 为什么每个学算法的人都绕不开并查集
1.1 并查集到底在解决什么问题
并查集这个中文名字其实已经把功能讲完了：处理“并”和“查”。所谓“并”，是把两个元素所在的集合合并成一个集合；所谓“查”，是查询某个元素当前属于哪个集合。更具体地说，它只支持两类操作：
- 给定两个元素 a 和 b，把 a 和 b 所在的集合合并。
- 给定两个元素 a 和 b，判断它们是否在同一个集合里。
它不支持“把一个元素从一个集合搬到另一个集合”，也不支持“删除集合中的某个元素”。如果你需要的操作是动点、删边、分裂集合，那并查集就不是最直接的工具。但反过来，如果问题只是反复地“连边”和“问是否连通”，并查集几乎是这个问题的最优解之一。
举个最常见的例子：现在有一个社交网络的模拟系统，里面有 N 个用户，每一次操作可能是“A 和 B 成为好友”，也可能是“查询 A 和 B 是否能够通过好友链条认识”。如果每次都用 BFS 重跑一遍图，单次查询就是 O(N + M)，N 一上来就扛不住。用并查集，每一次合并和查询的均摊时间基本可以认为是常数级别，这个差距在高频操作下会非常明显。
再用另一个场景加深直觉：你在做迷宫生成，很多生成算法里需要判断两个格子是否已经被同一个“连通区域”覆盖。如果每次都用 Flood Fill 去看，生成一张大迷宫的成本会高到离谱；用并查集维护“哪些格子已经连成一片”，每次判断只需要两三次数组访问和一次路径压缩。
可以说，并查集是“动态连通性”问题的标准答案。它不擅长做复杂统计，不擅长处理删除，但只要你面对的是不断合并集合、不断查询连通关系的场景，优先考虑并查集基本不会错。
1.2 路径压缩和按秩合并背后的时间复杂度直觉
很多人第一次看到并查集的实现时都会犯嘀咕：就这？一个数组加两个函数，复杂度怎么可能是 O(1) 级别的？
先别急着信，我们先看它朴素版本为什么慢。假如我们把每个集合看成一棵树，树的根就是集合的代表元素。每个节点只存自己的父节点。查询一个元素所在的集合，就要沿着父节点一路向上，直到走到根。合并两个集合时，直接把一棵树的根接到另一棵树的根下面。
问题在于，如果每次合并都无脑接，树的高度会失控。比如每次都把一棵高度较大的树往另一棵上挂，最终可能形成一条很长的链。链上有 10 万个节点时，查询尾部节点就要向上走 10 万步，那这和暴力遍历也没区别了。
于是有了两条经典优化：
- 路径压缩：在查询某个节点时，一旦找到了根，就把路径上遇到的所有节点的父节点直接改成根。下次再查这些节点，一步就能到根。
- 按秩合并：合并时把高度较小（或元素个数较少）的树挂到高度较大（或元素个数较多）的树上，避免树长歪。
这两条单独使用，复杂度分别是 O(log n) 级别；两条一起使用，均摊复杂度降到 O(alpha(n))，这里的 alpha(n) 是阿克曼函数的反函数。这个名字听起来很吓人，但它的增长速度极慢。当 n 是宇宙中的原子数量级别时，alpha(n) 也不会超过 5。所以你和别人说“并查集查找接近 O(1)”，在工程和竞赛里完全站得住脚。
到这里，我们已经把“为什么值得学”这个问题讲清楚了。接下来进入更硬核的部分：到底怎么设计 Find 和 Union，以及为什么合并不是简单地把两个父节点接一起。
2. 核心操作拆解：Find 和 Union 的设计思路
2.1 Find：沿着父指针找到根
并查集底层通常用一个数组 parent 来记录每个元素的父节点。初始时，每个元素的父节点指向它自己：
int parent[N]; for (int i = 0; i < N; i++) { parent[i] = i; }这种情况下，每个元素的根就是它自己，也代表它所在的集合。
Find 操作要回答的问题是：给定一个元素 x，它所在的集合的代表是谁？也就是要沿着 parent[x] 不断往上升，直到 parent[root] == root：
int find(int x) { while (parent[x] != x) { x = parent[x]; } return x; }这个版本能工作，但效率不高。真正的关键操作是在查找过程中把节点直接“压”到根下面，这就是路径压缩：
int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; }我见过不少初学者对这段代码有疑问：为什么递归返回之后，路径上每个节点的父节点都能被更新？因为递归是“先一路找到根，再沿着原路回退”。回退到某个节点时，它的 parent 已经被下一层更新成更靠近根的节点，最终一路更新成真正的根。
如果你不喜欢递归，也可以用迭代写法：
int find(int x) { int root = x; while (parent[root] != root) { root = parent[root]; } // 第二遍循环，把所有经过节点的父节点改成 root while (parent[x] != x) { int next = parent[x]; parent[x] = root; x = next; } return root; }两种写法指向同一个目的：减少树的深度。实际用哪种，主要看你对递归深度是否有顾虑。这个问题我在后面的“踩坑”章节会单独展开。
2.2 Union：先找根，再决定怎么接
Union 操作也很直白：让一个集合的根指向另一个集合的根。但问题是，谁指向谁？
如果没有任何策略，随便选一个根接到另一个根下面，最坏情况会形成一条链。正确的做法是按秩合并。这里的“秩”可以指树的高度，也可以指集合元素个数。下面用“按高度合并”写一个典型版本：
int rank[N]; // 初始全为 1，也可以理解成树高 void init(int n) { for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } } void unite(int x, int y) { int rx = find(x); int ry = find(y); if (rx == ry) return; if (rank[rx] < rank[ry]) { parent[rx] = ry; } else if (rank[rx] > rank[ry]) { parent[ry] = rx; } else { parent[ry] = rx; rank[rx]++; } }按高度合并的逻辑和二叉树保持平衡非常像：把矮树接到高树下面，不会增加高树的高度；只有两棵树一样高时，合并后高度才加一。这样即使不做路径压缩，树高也能保持在 O(log n) 左右。
还有很多人喜欢用“按大小合并”代替“按高度合并”，也就是把元素少的集合接到元素多的集合下面。理由是，除了能控制树高，还能顺手维护每个集合的 size，后面统计连通块大小时特别方便。代码上只是把 rank 数组换成 size 数组，合并时让 size 累加，其余思路完全一致。
2.3 为什么两个集合的根相同就不能再合并
很多人在写 Union 时会忽略一个前置检查：如果 find(x) 和 find(y) 已经返回同一个根，说明 x 和 y 已经在同一个集合里，此时不应该再做任何操作。
这个检查看起来简单，但在两类问题里特别重要。
第一类问题是“判环”。在无向图中，如果你要判断某条边是不是会让已有的连通块形成环，标准做法就是：遍历每条边，如果边的两个端点已经在同一个集合里，说明这两个点原本就连通，再加这条边就必然成环；否则就把两个集合合并。这里的“已经在同一个集合”就是环存在的最直接证据。
第二类问题是“维护连通分量数量”。服务器集群里有多少独立连通区域？社交网络里有多少个互相不联通的朋友圈？如果用一个变量 cnt 记录当前连通块数量，初始为 n，只有 Union 真的把两个不同集合合并时，cnt 才减一；如果 find 后发现根相同，cnt 不能变化。少了这个判断，统计就会出错。
所以说，Union 的正确套路是固定的：先分别 find，如果根相同就返回，否则才把两个根接起来。不要上来就 parent[find(x)] = find(y)，那会丢掉很多可以提前退出的信息。
3. 从零写一个并查集：代码演进与关键细节
3.1 朴素的数组版：十分钟能写出来的样子
先从最简单的实现看起。假设一共有 n 个元素，编号从 0 到 n-1。初始化、查找、合并三段代码加起来不到二十行：
class DSU: def __init__(self, n): self.parent = list(range(n)) def find(self, x): while self.parent[x] != x: x = self.parent[x] return x def union(self, x, y): rx = self.find(x) ry = self.find(y) if rx != ry: self.parent[rx] = ry这个版本连通性是能维护的，但性能不稳定。如果合并操作一直把后来的集合根接到第一个集合根下面，parent 数组会慢慢变成一条链。到那时，find(99999) 可能要循环上万次。这个版本只适合在教学演示或者数据规模极小的时候使用。
为了直观感受退化，可以看这个场景：依次执行 union(0,1)，union(0,2)，union(0,3)，直到 union(0,99999)。如果是上面代码的写法，每次都把前一个根指向本次新节点，最终 find(99999) 要一路跑回根。这样的复杂度从理论上讲就是 O(n)，和暴力没有任何区别。
所以竞赛或者工程里，朴素版基本只作为理解工具，真正的落地代码一定是带优化的。
3.2 路径压缩和按秩合并的完整写法
把前面两节的知识合到一起，一个能在绝大多数场景下放心使用的并查集长这样：
#include <vector> using namespace std; class DSU { public: vector<int> parent, rank; DSU(int n) { parent.resize(n); rank.resize(n, 1); 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]; } bool unite(int x, int y) { int rx = find(x); int ry = find(y); if (rx == ry) return false; if (rank[rx] < rank[ry]) { parent[rx] = ry; } else if (rank[rx] > rank[ry]) { parent[ry] = rx; } else { parent[ry] = rx; rank[rx]++; } return true; } bool same(int x, int y) { return find(x) == find(y); } };这里我把 unite 的返回值设成 bool。如果两个集合原本就已经连通，返回 false；如果成功完成合并，返回 true。这个设计在处理“判环”和“统计合并操作次数”时特别有用，不用在外面再调一次 find。
Python 版本同样可以直接对应：
class DSU: def __init__(self, n): self.parent = list(range(n)) self.rank = [1] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def unite(self, x, y): rx = self.find(x) ry = self.find(y) if rx == ry: return False if self.rank[rx] < self.rank[ry]: self.parent[rx] = ry elif self.rank[rx] > self.rank[ry]: self.parent[ry] = rx else: self.parent[ry] = rx self.rank[rx] += 1 return True def same(self, x, y): return self.find(x) == self.find(y)这段代码是我自己最常使用的模板。要注意的是，Python 的递归版本在极端数据下可能触及递归深度上限，后面踩坑部分会专门讲怎么改造成迭代版。
3.3 额外维护：集合大小、连通块数量、元素列表
基础并查集只是维护连通关系，但很多题目需要额外信息。最常用的是轮流问“当前最大的连通块有多少个元素”或者“合并了这么多次之后还剩多少个独立集合”。
维护集合大小很简单：新增一个 size 数组，初始全为 1。合并时，如果根不同，将新根的大小更新为两个集合大小之和，另一个根的大小清空或废弃即可：
vector<int> sz; // 只在根节点上有效 bool unite(int x, int y) { int rx = find(x); int ry = find(y); if (rx == ry) return false; if (sz[rx] < sz[ry]) swap(rx, ry); parent[ry] = rx; sz[rx] += sz[ry]; return true; }这里我直接采用了“按大小合并”，因为它比按高度合并更简单：不需要 rank 的加一逻辑，只需要维护 size。代码里还习惯性地把大的根统一放到 rx 上，这样后面写起来思路更清晰。
维护连通块数量同样简单：初始化 count = n，每次 unite 返回 true 时 count--。最后 count 是多少，就有多少个互不相同的集合。
如果你想更进一步，维护“每个集合具体包含哪些节点”，数组就有点吃力了。一般做法是维持一个 vector 数组，合并时把小的 vector 里的元素全部塞进大的 vector，也就是“启发式合并”。因为每个元素每次被搬进更大的集合，规模至少翻倍，所以总搬运次数是 O(n log n)。这是另外一套玩法，有兴趣的可以做一个小工具验证，这里不展开讲太多。
4. 把这几个经典题目吃透，并查集才算入门
4.1 连通块统计：朋友圈和省份数量
先看一类最直白的题目：给一个 n x n 的邻接矩阵，表示人与人之间是否直接认识，问有多少个“朋友圈”。按题意，朋友关系可以传递：A 认识 B，B 认识 C，那么 A 和 C 就在同一个朋友圈里。
这类题如果画成图，本质就是求无向图的连通分量数量。
用并查集来做，思路非常流畅：遍历所有用户对，只要两个人直接认识，就调用 unite(i, j)。最后遍历所有人，数一数有多少个根是不重复的。可以用一个 set 或者一个 visited 数组：
int count = 0; vector<int> visited(n, 0); for (int i = 0; i < n; i++) { int r = dsu.find(i); if (!visited[r]) { visited[r] = 1; count++; } }如果你在 unite 时已经维护了连通块数量 count，甚至可以少掉这一步，每次成功合并就自动减一。
这类题的核心价值在于：它告诉你不一定需要真的建图、跑搜索。只要关系可以传递，并查集就是一个更轻量的解法。
4.2 判断无向图是否成环：Kruskal 算法里的老朋友
另一个经典场景是判断一个无向图是否包含环。最原始的方法是用 DFS 加访问状态标记，但如果你拿到的是边集，而且需要动态判断，并查集往往更方便。
做法是：依次取出每条边，假设边的两个端点是 u 和 v。
- 如果 find(u) == find(v)，说明 u 和 v 已经连通。再加这条边，就形成了一个环，直接返回有环。
- 否则把这两个集合合并。
为什么这样成立？因为在无向图中，一条边的两个端点如果已经能通过其他路径到达彼此，那么这条边就是“多余”的，它会和原有路径构成一个闭合回路。
可以用一个很小的例子验证。假设有三条边：(0, 1)、(1, 2)、(2, 0)。
- 处理 (0, 1)：find(0) 和 find(1) 不同，合并。
- 处理 (1, 2)：find(1) 和 find(2) 不同，合并。此时 0、1、2 已在同一集合。
- 处理 (2, 0)：find(2) 等于 find(0)，发现已经在同一集合，所以存在环。
这个思路也是克鲁斯卡尔（Kruskal）最小生成树算法判环的底层逻辑。换句话说，你学会了并查集判环，回头再看最小生成树算法，很多代码一下就顺了。
4.3 反向离线：删除边比加边难得多
还有一个很容易被新手忽略的经典套路：动态删除边。如果我们面对的问题是“不断删除图中的边，并查询两个点是否连通”，直接用并查集做不了，因为并查集只擅长加边，不擅长删边。
但反过来想：把操作顺序倒过来。一开始先假设所有会被删除的边都已经删掉，把剩下的边用并查集全部合并；然后从最后一次操作往前处理。每一次“删除某条边”的操作，在倒序处理时就变成了“添加这条边”。
这是一个很漂亮的离线思想。很多题目会把一个看似“支持删边”的问题，转换成“倒过来加边”的问题，让并查集重新派上用场。具体处理时，通常需要先把所有操作读进来，记录哪些边在操作过程中被删掉，再倒序执行。这里的核心经验是：如果你发现题目要动态删边，先不要急着用复杂数据结构，想一想能不能把操作反过来做。
4.4 带权并查集：把差值关系也一起管理
普通的并查集只管“连不连通”，带权并查集则额外记录每个节点到集合根的“权值”，用来解决元素之间存在数值关系的问题。
举个例子：现在有一些变量，给定若干条关系“A 的值比 B 的值大 3”，然后查询“A 和 B 的差值是多少”。如果关系是兼容的，我们就可以把这些变量放进同一个并查集，并在 find 的过程中维护 weight[x]，表示 x 到根节点的相对值。
带权并查集的核心难点在 find 的路径压缩和合并时的偏移计算。
先看根节点到子节点的关系：原本每个节点的父亲是 p[x]，现在多一个数组 weight[x] 表示 x 到 p[x] 的差值。递归 find 时，先找到根，再递归返回，逐步更新：
int find(int x) { if (p[x] != x) { int root = find(p[x]); weight[x] += weight[p[x]]; p[x] = root; } return p[x]; }这里最容易写错的地方是：必须先递归 find(p[x])，让 p[x] 的权值先更新好，然后才能 weight[x] += weight[p[x]]。如果顺序反了，p[x] 还是老根，加出来的偏移就错了。
合并时，假设已知 x 和 y 的关系是 x 比 y 大 d，设 rx = find(x)，ry = find(y)，那么需要把 rx 挂到 ry 下面，然后推算出 weight[rx] 的值。
因为这个推导涉及正负方向，每个题的方向定义都可能不一样，我没有办法给一个万能公式。但有一个非常实用的经验：先画一条“根到节点”的有向链，把已知差值标在边上，然后从 x 到 rx、rx 到 ry、ry 到 y 的三段路径凑出“x 比 y 大 d”的等式，就能解出 weight[rx]。
带权并查集在竞赛里有很多变种，比如处理三分类关系的“种类并查集”，本质上就是把集合分裂成多个状态之后再用带权关系维护。学习路径上，建议先把不带权的题目刷熟，再进入带权部分，否则容易在 find 的顺序上栽跟头。
5. 实战中我踩过的坑：递归栈、离散化、以及 find 里的顺序
5.1 递归路径压缩在大数据量下的栈溢出
递归版本的 find 代码短、好看，但在 Python 和部分 C++ 场景下有一个隐患：递归深度受系统栈限制。
如果并查集的树已经很高，而你又没有按秩合并，或者某些合并顺序实在不够理想，一次 find 可能触发几千层甚至上万层递归。Python 默认递归深度大约是 1000，超过就抛异常；C++ 编译器默认栈空间也可能不够几万层递归。
我自己的做法是：在 Python 里，如果题目数据范围明显偏大，或者路径压缩前可能存在长链，直接用迭代版 find：
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这段代码有点长，但胜在没有任何递归深度问题。如果你始终同时使用路径压缩和按秩合并，其实递归深度也不会很大；但“不会”不等于“一定不会”，提前做个防御没什么坏处。
5.2 编号不连续或太大：先离散化
很多现实场景里，节点编号并不是整齐的 0 到 n-1。比如你可能拿到的是几十万条边的两个端点，端点编号是坐标值、订单号、IP 段甚至字符串。此时直接开数组根本开不下。
解决办法是离散化：把用到的所有节点编号收集起来，排序去重，然后映射到从 0 开始的连续编号。
vector<int> all; for (auto &e : edges) { all.push_back(e.u); all.push_back(e.v); } sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); auto getId = [&](int x) -> int { return lower_bound(all.begin(), all.end(), x) - all.begin(); };之后所有并查集操作都基于 getId(x) 进行，原始编号是什么并不重要。需要注意的坑是：一定要先把所有将来会出现的编号收集完再做映射，不能边读边动态映射。因为你输入的边可能包含某些编号在比较靠后的查询里才出现，提前映射会漏点。
如果编号是字符串，也可以先用哈希表映射成整数，再走同样流程。总之，并查集本身只关心“相对关系”，不关心节点叫什么名字，离散化不影响正确性。
5.3 带权并查集的 find 更新顺序错一位，结果全错
最后再讲一个我见过最隐蔽的 bug：带权并查集里，find 递归时如果没有先把父节点的权值更新好，就直接拿旧权值去加，那么整棵子树的偏移都会错。
看一类错误写法：
int badFind(int x) { if (p[x] != x) { weight[x] += weight[p[x]]; // 此时 p[x] 的权值还没更新 p[x] = find(p[x]); } return p[x]; }如果 p[x] 本身不是根，weight[p[x]] 表示的只是 p[x] 到它自己父节点的差值，而不是 p[x] 到根的差值。这一步算完，weight[x] 就变成了一个和历史路径对不上的值。等到之后 p[x] 再被更新为根，weight[x] 已经“回不去了”。
正确的顺序必须先递归更新父节点，再用更新后的值累加：
int goodFind(int x) { if (p[x] != x) { int root = goodFind(p[x]); weight[x] += weight[p[x]]; p[x] = root; } return p[x]; }这里默认 weight[p[x]] 在递归完成后已经代表 p[x] 到集合根的差值，所以 weight[x] 加上它就能得到 x 到集合根的差值。
我在实际写带权并查集时，会习惯性在纸上先画一棵三层的小树：根 r，中间节点 m，叶子 x。手动推一遍 find(x) 前后 weight 的变化，确认每一步更新顺序，然后才动手写代码。这个习惯帮我避免了很多次“跑样例没问题，一交就错”的惨案。
如果你也正在练并查集，我建议按这个顺序走：先手写朴素版弄清楚数组和根的关系，再把路径压缩和按秩合并一起加上，然后做两类经典题（连通块统计、判环），接着尝试反向离线的思路，最后再挑战带权并查集。每一步都用小例子验证自己的代码，比看十篇理论讲解都管用。毕竟并查集这个数据结构，写几遍之后的肌肉记忆，比背模板可靠得多。
