企业官网建设流程全解析

说实话，我第一次看到“查并集”这个名字的时候，下意识把它拆成了“查找”和“集合”两部分，心里还嘀咕：这不就是遍历吗？后来在某次带新人写网络连通性检测需求时才彻底改观——对方用邻接表存边，每次查询都从起点重新跑一遍DFS，数据量到两万就肉眼可见地卡顿。我建议他把那部分换成查并集之后，查询从“重跑全图”变成了“查一次根节点”，耗时几乎归零。

查并集，业内更常叫“并查集”，英文是 Union-Find。它解决的场景说穿了就一句话：元素之间陆续建立关系，随时要判断两个元素是否已经在同一个集合里。这个问题看起来简单，但高效解法不靠扫描，而是靠维护一棵棵“代表树”。这篇文章我从原理讲到优化，再讲到常见变体和真实题目怎么拆，希望能帮正在学算法、准备面试、或者工作中需要处理动态连通性的朋友，一次把查并集吃透。

1. 查并集到底在解决什么问题：集合合并与连通性查询

1.1 一个看似简单、写起来却很难快的场景

先还原一个最常见的入门例子。假设你有一群人，彼此之间会“成为朋友”。朋友关系有传递性：A同学和B同学是朋友，B同学和C同学是朋友，那A同学和C同学也被认为是朋友圈子里的。现在会不断出现新关系，同时有人不断来问：D同学和E同学在不在同一个朋友圈？

用普通关系表存，很简单：每次出现新关系，就加一条边；每次查询，从D做一次BFS或DFS，看能不能走到E。问题出在查询多了以后。如果图里有10万个点、20万条边，一次查询最坏就是20万的复杂度，来了1万次查询就是2亿次操作，现场基本就卡死了。

查并集的思路完全不同：它不保存“谁和谁是朋友”这种原始关系，而是直接维护“每个人属于哪个朋友圈代表”。每次新关系加入时，把两个朋友圈合并成一个；每次查询时，只问“两个人的代表是不是同一个”。这样一来，关系的建立变成了合并操作，查询变成了找根操作，不需要扫整张图。

1.2 查并集的正式定义与核心操作

查并集是维护若干不相交集合的数据结构。注意“不相交”三个字：每个元素只属于一个集合，集合之间没有重叠。这个特性决定了它的接口必须围绕“合并集合”和“查询归属”设计，而不是围绕“修改集合内容”。

它只有三个基本操作：

• makeSet(n)：初始化n个元素，每个元素单独成一个集合。
• find(x)：找到x所在集合的“代表元素”，有时也叫根。
• unite(x, y)：把x所在集合和y所在集合合并成一个。如果它们已经在一个集合里，这个操作可以什么都不做。

每个集合用一棵树来表示，树的根就是集合的代表。这里有个反直觉的点：查并集并不关心树长什么样，它只关心根是谁。你不需要知道一个集合里都有哪些成员，也不关心树是宽是扁，只要能通过任意成员快速摸到根，就能判断两个元素是否在同一个集合里。

这个“只关心根”的设计，是查并集能快起来的关键。很多初学者想不通为什么不用哈希表维护“集合到成员列表”的映射，因为那样合并集合时要遍历成员、搬来搬去，复杂度是集合规模级别的。查并集把合并成本降到了“只用动一个指针”，代价就是放弃了“快速枚举集合成员”的能力。

1.3 适用边界：什么时候不该用并查集

搞清楚什么时候不能用它，和知道它什么时候好用同样重要。我列几个典型的不适用场景。

• 需要删除或者分裂集合。查并集只会合并，不会拆开。如果题目要求把某个集合拆成两个，或者把元素从集合里删掉，那查并集就帮不上忙，得换更重的数据结构或者加额外的“惰性删除”标记。
• 需要拿到集合内的全部元素。比如“输出哪些用户属于同一个群组”，查并集不能满足，它本身不维护成员列表。这种题应该考虑用哈希表维护“根到成员集合”的映射，合并时把小集合的元素搬进大集合，也就是启发式合并。
• 只查询不合并，且查询量巨大。这种情况可以先用并查集或BFS把连通分量预处理出来，之后每次查询直接查分量编号，连find都不用。
• 元素之间的关系不是等价关系。比如“A大于B”这种偏序关系，靠普通查并集没法表达，需要带权并查集或者其他结构。

换句话说，查并集是给“动态加边、静态问连通”的场景量身定做的。如果你发现题目里边的数量只增不减，那就大概率能用上它。

2. 一维数组里藏着一片森林：从最朴素的实现看核心机制

2.1 用“每个元素只知道自己的老大”维护集合

查并集的经典实现，只用一维数组parent。parent[i]存的是i的父节点：你可以把它理解成“每个人只登记了自己的直接上级”。往上不断找，直到某个人的上级是自己，那这个人就是根，也就是集合的代表。

为什么记录“上级”而不是“下级”？因为合并的时候，我们只需要让一棵树的根指向另一棵树的根。如果记录“下级”，想找根就得先枚举集合成员，那就又变回遍历了。记录“上级”，任何一个元素都能在树上往上爬，爬到动不了的地方就是根。

初始化时，parent[i] = i，意思是每个元素自己当根。这个细节千万别省，很多 bug 都是初始化没做好，导致 find 死循环。

2.2 find 和 unite 的直观代码

最朴素的写法大概长这样，我先不给任何优化，方便看清楚核心机制。

vector<int> parent; int find(int x) { while (parent[x] != x) x = parent[x]; return x; } void unite(int a, int b) { int ra = find(a), rb = find(b); if (ra != rb) { parent[ra] = rb; // 把a的根接到b的根上 } }

注意一个容易踩的小坑：C++ 里union是关键字，所以函数名不能叫union，否则编译直接报错。我用的是unite，很多资料里也会写成merge或Union（首字母大写避开关键字）。

判断两个元素是否在同一个集合，代码就是：

bool same(int a, int b) { return find(a) == find(b); }

这台朴素代码在数据量小的时候没什么问题，但一旦遇到恶意数据，它的性能会退化到让人怀疑人生。

2.3 朴素实现为什么会被卡成一条链

问题出在unite里那句parent[ra] = rb。如果每次合并都碰巧让“已经合并过的集合根”指向“新的集合根”，树就会不断长高。举个例子：依次执行unite(1,2)、unite(2,3)、unite(3,4)，如果每次都是把旧集合的根接到新集合的根上，就会形成一条链：4 → 3 → 2 → 1。

这时候find(4)要一路从4走到1，复杂度是O(n)。如果m次操作都这么干，总复杂度就是O(mn)。一万个元素、一万次操作，看起来不多，实际跑起来已经能感觉到明显的延迟；如果到十万级别，基本就跑不动了。

这个退化问题的根源是：树的高度没有任何控制。接下来的两个经典优化，本质上都是为了让树变得更矮。理解了这一点，你就能明白为什么优化方案叫“路径压缩”和“按秩合并”。

3. 复杂度接近常数的两个关键优化：路径压缩与按秩合并

3.1 路径压缩：边走边问，顺便把路踏平

第一个优化叫路径压缩，思路非常直接：既然find要顺着链往上走，那走完一趟之后，干脆把路径上所有节点都直接挂到根下面。这样下次再查这些节点时，一步就能摸到根。

递归写法非常优雅：

int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 递归返回时，一路把节点挂到根 } return parent[x]; }

如果你担心递归爆栈，也可以用循环版本，分两步走：先找到根，再重新走一遍路径，把沿途节点的父指针全部指向根。

int find(int x) { int root = x; while (parent[root] != root) root = parent[root]; while (x != root) { int nxt = parent[x]; parent[x] = root; x = nxt; } return root; }

两种写法效果一样：一次find之后，整条链被拍平，树变得非常矮。这样做的代价只是这一次多走了一遍路径，收益却是之后所有访问这些节点的时间都变成几乎O(1)。

3.2 按秩合并：让小树长到大树上

路径压缩只是让“查过的路径”变矮，但如果没有路径压缩的那部分节点，它们所在的树仍然可能很高。所以还需要第二个优化：合并时让小树的根挂到大树的根下面。这个“大小”可以用树的节点数，也可以用树的高度，业内统称为秩。

我用节点数size来当秩，写起来最直观：

vector<int> parent, sz; // sz[i] 只对根有意义 int find(int x) { /* 路径压缩版本 */ } 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); // 保证ra是较大的集合 parent[rb] = ra; sz[ra] += sz[rb]; }

把小的挂到大的下面，效果是：每次合并后，树的高度最多增加一层，而且是较低的那棵树整体深度加1。严格来说，按秩合并单独使用就能保证树高是O(log n)。

这里有个细节值得点出来：按秩合并不需要精确维护“高度”，因为路径压缩随时会改变树的形状，rank信息本来就“过期”了。用size做启发式足够稳健，代码也简单。很多教材会把rank定义成“高度上界”，这只是理论上的严谨，实操中size反而是最不容易出错的选择。

3.3 两者的复杂度结论与工程选择

在讲复杂度之前，我先把两个优化单独和组合的效果列成一张表，方便你对照。

这里的α(n)是反阿克曼函数，增长极慢，在一切现实数据规模下都不会超过4，所以你可以放心地把“两个优化一起用”的并查集当成O(1)来看。这个概念可能有点抽象，我换个说法：就算你有一个宇宙原子总数那么多的元素，α(n)也不会超过5。

为什么两个优化要一起用？因为路径压缩负责“让查过的路变平”，按秩合并负责“让没查过的路不至于太深”，两者管的事情不一样。只做路径压缩，理论上构造特殊数据还是可以卡掉；只做按秩合并，复杂度虽然也是O(log n)，但常数比组合起来要大。既然两个优化加起来就几行代码，没必要省。

4. 可直接抄走的代码封装与高频易错点

4.1 C++ 与 Python 参考实现

我自己在项目里会直接把查并集封装成一个类，接口尽量少而明确：find、unite、same。unite返回布尔值表示“这次合并是否真的发生了合并”，这个返回值在很多题目里非常有用，后面实战部分会反复用到。

C++ 完整版本：

class DSU { private: vector<int> parent, sz; public: DSU(int n) : parent(n), sz(n, 1) { iota(parent.begin(), parent.end(), 0); } int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } bool unite(int a, int b) { int ra = find(a); int 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; } bool same(int a, int b) { return find(a) == find(b); } };

Python 版本，我用循环find，避免递归在极端数据下触发最大递归深度错误：

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 x != root: 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 True

一个小细节：初始化的 n 要确保能覆盖所有可能出现的下标。如果题目输入是1-indexed（也就是说点编号从1开始），最好申请 n + 1 的大小，不然初始化只到 n-1，后面访问 parent[n] 就会越界或越出数组。

4.2 五个高频坑：从“忘写find”到合并方向

经验多了之后，我发现初学者在并查集上踩的坑高度集中，这里列五个最典型的，都值得记一下。

坑一：判断是否同一集合时只比较 parent[a] == parent[b]。这是最常见的错误。parent[a] 只是a的直接上级，不是根。只有经过路径压缩之后，a的父节点才可能恰好等于根；在没压缩的地方，这个判断就是错的。正确做法永远是 find(a) == find(b)。

坑二：unite 里忘了先 find。直接写parent[a] = b会把a从它原来的集合里拎出来挂到b下面，根本没合并两个集合，而是把a的个人归属改了。合并之前必须先拿到两个集合的根，再改根之间的指针。

坑三：find 用递归，在极端数据下爆栈。Python 尤其容易触发 RecursionError。我的习惯是：能用循环就用循环；C++ 递归深度一般问题不大，但如果 n 到百万级别且数据退化，建议也换成循环版。

坑四：初始化数组时下标没对齐。有的题目元素编号从1开始，有的从0开始。初始化长度、遍历起点、查并集下标都要跟题目的编号规则保持一致，否则会出现“找不到自己的根”这种诡异问题。

坑五：按秩合并时只更新 not root 的 parent，忘了更新新根的 size。虽然size只对根有意义，但如果你把rb挂到ra下面却忘了sz[ra] += sz[rb]，后面按size做合并时，判断谁大谁小就会失真，最终影响树高。我现在写完unite都会顺手检查一遍：根是否变了、大小是否累加了、返回值是否写对。

5. 实战拆解：三类典型问题的解题思路

5.1 连通块计数

并查集最直接的实战就是统计连通块数量。比如某个系统里有n台设备，已知若干设备之间能直接通信，问整个网络被分成了几个独立的子网。这里的“连通块”就是“互相可达的设备集合”。

用并查集的解法是：先把每个点初始化成独立集合，然后依次把所有通信关系unite。unite 返回 true 说明两个设备原本不在一个集合，这次合并让连通块数量减少了1。于是：

int components = n; for (每条边(a, b)) { if (dsu.unite(a, b)) { components--; } } // 最终的 components 就是连通块数量

这个技巧也可以反过来用：如果想知道“某两个点是否已经连通”，直接用same判断即可。连通块计数配合路径压缩，合n个点、m条边的时间接近O(n + m)，比反复BFS不知道快到哪里去了。

5.2 Kruskal 最小生成树

最小生成树问题里，并查集是判环的核心工具。Kruskal算法的思路是：把边按权值从小到大排序，从最小边开始一条条尝试加入；如果这条边的两个端点已经连通，说明加入它会产生环，必须跳过；否则就加入它，并把这个连接关系合并进集合。

这里“是否已经连通”的判断，正是查并集最擅长的部分。整体伪代码如下：

sort(edges.begin(), edges.end(), cmp); DSU dsu(n); int cost = 0, cnt = 0; for (auto &e : edges) { if (dsu.unite(e.u, e.v)) { cost += e.w; cnt++; if (cnt == n - 1) break; // 已经形成最小生成树 } }

你只需要记住一个结论：并查集在Kruskal里的角色，就是“用接近O(1)的时间检查一条边会不会形成环”。换成DFS或BFS做法，每条边都要扫一次全图，复杂度直接变成O(E(V+E))，在大图上根本跑不动。

5.3 离线问题与反向加边

还有一种套路也值得单独拿出来说：题目不是“加边问连通”，而是“删边问连通”。删边对并查集来说是逆操作，不能直接做，但我们可以把操作倒着看。

举个具体场景：某个城市的路网中，一开始所有道路都存在，接下来会发生一系列事件，有的是“某条路被关闭”，有的是“查询某两个地点是否仍然连通”。如果正着处理，每删一条边都要重新检查连通性，非常难写；反过来呢？先把所有道路删除的操作执行完，得到一个最终的静态路网，用并查集把“最终仍然连通”的关系建立好，然后从最后一个事件往前处理：

• 碰到“查询某两点是否连通”就用same(a, b)直接回答；
• 碰到“某条路在这个时间点被关闭”这个事件，对应到倒序处理时，就是把这条路“加回去”，执行unite。

这种“正难则反”的技巧，在P2P连接维护、断网恢复、动态图问题里都很常见。处理的难点往往在于：读入所有操作后，要先把所有“最终可能还存在的边”预处理好，再把操作倒序遍历。顺序搞反了，答案就全是反的。

6. 进阶变体：带权并查集、反集与可撤销并查集

6.1 带权并查集：维护“到根的距离”

普通并查集只告诉你“两个元素在不在同一个集合”，带权并查集还能告诉你“元素之间的关系是什么样的”。它比普通版多维护一个值：每个节点到父节点的“权值”。这个权值可以表示距离、差值、或者是某种相对关系。

路径压缩时，要顺带把权值累加。比如find实现成这样：

vector<int> parent, weight; // weight[x] 表示x到parent[x]的权值 int find(int x) { if (parent[x] != x) { int old = parent[x]; parent[x] = find(old); weight[x] += weight[old]; // 路径压缩后，weight[x]变成到根的距离 } return parent[x]; }

合并的时候，如果想把根 ra 挂到根 rb 上，需要根据已知条件反推 ra 到 rb 的权值。这个推导很容易出错，所以我一般先在纸上把关系图画出来，再写表达式。

带权并查集最经典的应用是“食物链”类问题：几种生物之间存在“同类、吃、被吃”的循环关系。解法是把关系抽象成模3的余数，每次合并或判断都检查权值是否冲突。这类题目对思维要求比较高，但一旦想通“权值表示到根的相对关系”，套路就固定了。

6.2 反集：用一个数组装下两类对立关系

有些问题里，元素之间的关系不是“朋友”而是“敌人”，比如“敌人的敌人是朋友”。普通并查集只能表达“同一阵营”，反集就是用来表达“一定不同阵营”的。

实现方式很巧妙：把空间扩大一倍，前n个位置表示“元素本身阵营”，后n个位置表示“该元素的敌对阵营”。如果x和y是敌人，就执行：

unite(x, y + n); unite(x + n, y);

这样构造出来后，如果 find(x) == find(y)，说明x和y在同一个阵营，这与“敌人”关系冲突。如果用same(x, y + n)判断，则说明x和y当前对立关系成立。

经典真题“关押罪犯”就是反集思路：把仇恨值大的两个罪犯尽量分开关，每次合并他们的敌对关系，一旦出现无法避免的冲突，那个仇恨值就是答案。我建议你遇到“必须让两个元素不在同一集合”的题目，第一反应就想到反集。

6.3 可撤销并查集：当答题需要“后悔”时

普通并查集的合并操作“做了就回不了头”，因为路径压缩会同时修改很多节点的父指针。可撤销并查集的思路是：放弃路径压缩，只用按秩合并，然后用栈记录下每次合并到底改了哪些变量。

为什么不能路径压缩？因为路径压缩会修改大量父指针，想把它们全部还原回来，成本太高。只用按秩合并时，每次unite最多只修改两个变量：小树的根节点指向大树（改一次parent），大树的size增加（改一次size）。把这些旧值压入栈，撤销时弹栈恢复即可。

struct Change { int pos; // 被修改的节点下标 int old_parent; int old_size; }; stack<Change> st; void rollback() { Change c = st.top(); st.pop(); parent[c.pos] = c.old_parent; // 同时还要找到c.pos原来的容器根，把它的size减回去 }

可撤销并查集的单次操作复杂度是O(log n)，因为按秩合并保证了树高有界。它主要用在离线分治、搜索回溯、以及某些需要“试错”的算法里。如果你只是普通做题，暂时用不上，但知道有这么一个变体，遇到需要回溯的题目时就不会抓瞎。

最后说点个人体会。我写查并集的习惯，是尽量把find、unite、same三个接口拆得干干净净，unite固定返回bool，这样连通块计数和Kruskal里都不用额外写判断。第二个习惯是递归find和循环find二选一时，默认选循环，尤其是Python，能少踩一个RecursionError就是少踩一个。第三个习惯是合并时再检查一遍“大小集合方向”，宁可多写一个swap，也不要为了省代码忘记按秩合并。这些细节看起来琐碎，但真正遇到十万级数据、调试到深夜时，一个顺手的好实现能帮你省下大量时间。