企业官网建设流程全解析

第一次在算法课作业里见到并查集，我盯着那二十来行代码看了半天，心里嘀咕：就这么点东西，也能算一个数据结构？一个数组、两个函数，扫一眼就懂了。结果后来不管是做Kruskal最小生成树、判朋友圈连通性、处理编译原理里的变量等价类，还是在面试题和算法竞赛里碰上“给关系和矛盾”的题目，绕来绕去，最后都会落到并查集身上。它就像一个低调的底层工具，代码不炫技，但很多看起来复杂的场景，一旦想到“用并查集”这个方向，解决方案就瞬间清爽了。今天我把并查集从最基础的实现、复杂度分析到带权并查集推导，再到实际写代码时容易踩的坑，完整拆开讲一遍。期末复习、考研408补基础、刷LeetCode想补强这块的人，看完这篇基本够了。

1. 并查集到底在解决什么问题

1.1 先看一个最典型的应用场景

假设你现在做一个社交应用的后台，用户之间有“好友关系”，你要快速回答“A和B是不是同一个圈子的人”。圈子怎么定义？好友的好友也算好友，也就是说，只要两个人之间存在一条关系链，他们就被看成同一个连通团体。这就是典型的连通性问题。

换个更经典的场景：一张无向图，有n个顶点和m条边，需要判断两个顶点是否连通。或者反过来，一开始所有点互相独立，你不断把两个点连起来，随时查询两个点的连通状态。

这种需求用普通的数据结构并不好办。数组存邻接表，查一次连通性要做一次BFS或DFS，复杂度跟图的大小直接挂钩。而并查集的思路完全不同：它不关心两个点之间是怎么连通的，只维护“属于同一个集合”这个事实。所以查询两个点是否连通，只需要沿着它们各自的关系链往上一层一层找，看看最终找到的“根”是不是同一个。

这个抽象方向很重要：并查集牺牲了对关系路径的记录，换来了动态合并与动态查询的高效。现实中大多数问题也只关心“连不连通”，并不需要路径本身，因此这种取舍非常划算。

1.2 为什么不能用普通的哈希表或集合

有人会问：既然要维护“集合”，我直接用哈希表存多个集合不行吗？比如维护一个“集合编号”到成员的映射，合并两个集合时把一个集合的所有元素搬到另一个集合里去。

思路可行，但代价很高。合并操作平均要移动一个集合里一半的元素，遇到连续合并n次的场景，最坏情况下总复杂度退化成O(n²)。面试题里数据量一旦到十万、百万级别，直接超时。

并查集反着来，它用一棵树来表示一个集合。树的根节点就是集合的代表，每个节点只需要记录自己的父节点。合并两个集合时，只需要把其中一棵树的根指向另一棵树的根。注意，这里没有移动任何成员节点，只是改了根的一个指针。查询归属时，沿着父指针往上找根即可。整个过程的代价几乎只取决于树的高度，而通过路径压缩和按秩合并，这个高度可以被压到近乎常数级别。

用一句话概括核心思想：普通集合关心“里面有什么”，并查集只关心“谁是老大”。只要老大相同，就认为成员在同一个集合里。

1.3 并查集适合的问题类型与个人判断经验

我在实际应用中总结出一套判断方法：只要题目里出现“若干元素之间满足某种等价关系”“把元素划分为若干互不相交的组”“动态添加关系后查询两个元素是否相关”，大概率就能用并查集。

几个常见方向：

• 图论中的连通分量统计、最小生成树Kruskal算法判环
• 社交网络里的群组划分、共同好友判断
• 数据库或编译原理中的等价类划分，比如判断两个变量是否同一类型
• 离线查询中的“时间倒流”问题，配合反向删除技巧处理
• 带权扩展后，处理“相对关系”类题目，比如同类、吃与被吃的关系

判断方法有了，接下来就进入核心实现环节。

2. 核心实现：十几行代码如何做到近乎常数时间

2.1 最基础的数组实现与两个核心操作

并查集的物理存储极其朴素：一个一维数组parent，parent[i]表示节点i的父节点。初始时每个节点的父节点是自己，表示每个元素单独成一个集合，自己就是自己的“老大”。

两个核心操作分别是find和union。

find(x)要做的，是不断沿着parent[x]向上跳，直到找到根节点，也就是满足parent[x] == x的那个节点。查找结果就是这个元素所属集合的代表元素。

union(x, y)则先分别找到x和y的根节点，如果根不同，就把其中一个根挂在另一个根下面。这样两个集合合并成一个，下次find时，双方都会找到同一个根。

基础实现代码：

class DSU { private: vector<int> parent; public: DSU(int n) : parent(n) { for (int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { while (parent[x] != x) x = parent[x]; return x; } void unite(int x, int y) { int rx = find(x); int ry = find(y); if (rx != ry) parent[ry] = rx; } bool isConnected(int x, int y) { return find(x) == find(y); } };

这个版本已经能解决连通性问题了，但性能不一定稳。问题在于，如果合并顺序不理想，树会退化成一个长链。比如把0挂在1下面、再把1挂在2下面，最后find(0)要一路走到链尾，查询复杂度变成O(n)。数据量大时，这种退化无法接受。

2.2 路径压缩：让每个节点直接指向根

路径压缩的思路很简单：在find的过程中，把沿途经过的每个节点都直接挂到根节点下面。这样下次再查询这些节点时，一步就能到达根。

代码上只需要一行递归：

int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }

这个方法叫做“递归式路径压缩”，每次查询会把整条路径上的节点全部“拍平”。如果担心递归深度过大，也可以写迭代版本：

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

我实测下来，递归版本在绝大多数场景都没问题，真出现爆栈也几乎都是因为树退化到极致，而加上了路径压缩之后，这种退化几乎不存在。迭代版的好处是没有任何递归开销，适合在嵌入式或极端环境下使用，但代码可读性稍差。

路径压缩的核心价值在于：查询操作不只是“找到老大”，它还在顺手优化整棵树的结构。越查越平，越查越快。

2.3 按秩合并：为什么能让树更矮

路径压缩解决的是查询路径变长的问题，但它有一个盲区：如果在很深的树结构上反复调用union，每次union都要提前先find，这个find会触发路径压缩，所以整体还好。不过，如果能从一开始就控制树的高度，让合并有序进行，效果会更好。这就是按秩合并。

所谓“秩”，通常指树的高度，也可以用子树大小。合并两个集合时，把高度小的树挂到高度大的树下面。如果两棵树高度相同，随便选一棵挂到另一棵下面，被挂的那棵树高度加一。

实现代码：

class DSU { private: vector<int> parent, rank_; public: DSU(int n) : parent(n), rank_(n, 0) { for (int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void unite(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return; if (rank_[rx] < rank_[ry]) swap(rx, ry); parent[ry] = rx; if (rank_[rx] == rank_[ry]) rank_[rx]++; } };

路径压缩加按秩合并，两个优化一起上，并查集的单次操作均摊复杂度是O(α(n))，这里的α是反阿克曼函数。这个函数增长慢到什么程度呢？n取宇宙中原子数量级别的数字，α(n)也超不过5。所以工程上可以放心地认为，并查集的单次操作就是常数时间。

2.4 复杂度分析里最容易困惑的点

很多人背结论“并查集复杂度是O(α(n))”，但不知道这个结论成立是有前提的，那就是路径压缩和按秩合并必须同时使用。只做路径压缩不做按秩合并，或者只按秩合并不压缩路径，都能让复杂度退化。前者在极端数据下会退化到O(m log n)，后者则退化成O(n)级别的单次查询。

另外注意，复杂度里的n是节点总数，m是操作总数。整个并查集的构建和一系列操作的总复杂度可以写成O(m α(n))，但这里“均摊”的意义和普通数据结构里的均摊不太一样。如果不做路径压缩，只使用按秩合并，单次查询最坏情况下依然是O(log n)，也就是说查询仍然和树高相关。只有同时使用路径压缩，摊还复杂度才能压到反阿克曼函数级别。

这个细节，考研408和面试里都很喜欢问。

3. 我带一个实战：用并查集实现Kruskal最小生成树

3.1 Kruskal为什么必须用并查集

最小生成树问题，目标是在一张带权无向图里选n-1条边，把所有点连起来，同时保证总边权最小。Kruskal算法的贪心策略是：把全部边按权值从小到大排序，依次遍历，每次尝试把边的两个端点“连起来”，但前提是这两个端点之前还没有被连通过。

这里就涉及一个高频判断：当前边的两个端点是否已经属于同一个连通分量。如果属于，加入这条边会形成环，必须跳过。如果不属于，就加入这条边，并合并两个连通分量。

这个“判断+合并”的需求，几乎是为并查集量身定制的。用其他结构做，要么代码复杂度高，要么时间复杂度高。Kruskal排序部分O(m log m)，而并查集部分只需要O(m α(n))，整体复杂度由排序主导，效率很高。

3.2 完整代码与关键步骤推导

struct Edge { int u, v, w; bool operator<(const Edge &other) const { return w < other.w; } }; class DSU { private: vector<int> parent, rank_; public: DSU(int n) : parent(n), rank_(n, 0) { for (int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } bool unite(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return false; if (rank_[rx] < rank_[ry]) swap(rx, ry); parent[ry] = rx; if (rank_[rx] == rank_[ry]) rank_[rx]++; return true; } }; int kruskal(int n, vector<Edge> &edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int ans = 0, cnt = 0; for (const Edge &e : edges) { if (dsu.unite(e.u, e.v)) { ans += e.w; cnt++; if (cnt == n - 1) break; } } return cnt == n - 1 ? ans : -1; }

这里我把unite设计成返回bool，成功合并返回true，已经在同一集合返回false。这个返回值在Kruskal里非常有用，省去额外调用isConnected再unite的两步操作，效率更高，逻辑也更紧凑。

3.3 排序选边时并查集的调用时机

这里有个很多人忽略的细节：Kruskal必须先把所有边按权值排序。排序之后才进入并查集的循环。为什么不能按输入顺序直接处理？因为Kruskal的正确性依赖于贪心选择当前最小权值的边，而只有排序后才能保证每次拿到的是当前可选的最小边。

回到并查集这边，每次遍历到一条边，就调用find检查两个端点的根。这里注意一个优化：先调用find，把两个根的编号记录下来，再做合并，可以避免unite内部重复find一次。虽然并查集的find很快，但竞赛或者面试里，这种细节点出来会让代码的档次提升不少。

我自己写这个的时候经常犯一个低级错误：忘记判断n个点最终是否连成了一棵完整的树，也就是cnt是否等于n-1。如果图本身不连通，Kruskal不可能生成完整的生成树，此时应该返回失败标志。真正写工程代码时，这个返回值要明确交给上层处理。

一个实用的小技巧：如果你在写实验报告，经典问题“Kruskal算法为什么要用并查集而不直接用深度优先搜索判断环”，答案不是并查集更快，而是它天然能维护动态连通分量。DFS每加入一条边都要做一次全图中环的判断，单次复杂度O(n+m)，串起来之后就变成O(m(n+m))，在稠密图里非常吃亏。

4. 进阶：带权并查集怎么处理关系冲突

4.1 带权并查集的适用模型

基础并查集只维护“是否属于同一个集合”，信息量有限。但很多实际问题里，元素之间的关系不只是“相连”或“不相连”，还有相对方向、相对大小、状态差异。比如三国关系里的同类、吃与被吃，或者一个班级里两两之间的成绩高低关系。

这时就需要带权并查集，也就是在并查集的每条边上维护一个权值。每个节点除了存父节点，还要存一个到父节点的权值。这个权值不是物理距离，而是一种“逻辑偏移量”，用来表示当前节点与父节点之间的相对关系。

我带的最常见例子是经典的食物链问题：三类动物，可能处于“同类”“A吃B”“A被B吃”三种关系。题目会给出若干条已知关系，有些关系是正确的，有些是错误的，要求统计错误关系的数量。

这里需要把三种关系映射成数字0、1、2，再通过模3运算传递关系。映射规则不是唯一的，但你一旦定下规则，整个推导过程所有公式都要围绕这个规则走。

4.2 关系定义与向量偏移法

我在代码里习惯这样定义：

• weight[x]表示节点x到其父节点parent[x]的关系，取值为0、1、2
• 0表示x与父节点是同类
• 1表示x被父节点吃
• 2表示x吃父节点

利用模3加减法，可以从一个节点一路推到根节点。比如x到根节点r的关系，就要把x到parent[x]的关系、parent[x]到grandparent[x]的关系一路累加起来，每累加一次对3取模。

如果x和y已经属于同一个集合，说明它们之间已经存在一条经过根的路径，可以把x和y之间的相对关系算出来，再断言它和题目给出的新关系是否一致。如果一致，这条关系是正确的，否则就是错误关系。

如果x和y不在同一个集合，说明这条关系是新信息，要把两个集合合并起来，同时根据给定的关系推导出被挂根节点到另一个根节点的权值。

这就是带权并查集在处理“关系冲突判定”问题上的核心流程。

4.3 核心代码与公式推导

class WeightedDSU { private: vector<int> parent, 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 (parent[x] == x) return x; int root = find(parent[x]); weight[x] = (weight[x] + weight[parent[x]]) % 3; return parent[x] = root; } bool unite(int x, int y, int rel) { // 表示：x与y的关系为rel，这里定义0=同类，1=x吃y，2=x被y吃 int rx = find(x), ry = find(y); if (rx == ry) { return (weight[y] - weight[x] + 3) % 3 == rel; } parent[ry] = rx; weight[ry] = (weight[x] + rel - weight[y] + 3) % 3; return true; } };

这个公式怎么来，我手把手推一遍。合并时，把ry这棵树的根挂在rx下面，也就是parent[ry] = rx。问题变成：ry到rx的权值weight[ry]应该等于多少，才能保证节点y到rx的总关系与x到rx的总关系之差，等于题目给定的rel。

从y出发，经ry再到根rx的总权值是weight[y] + weight[ry]。从x出发，经rx到根rx的总权值就是weight[x]。它们之间的差值需要满足：

(w[y] + w[ry] - w[x]) % 3 = rel

解这个同余式：

(w[ry]) % 3 = (rel + w[x] - w[y]) % 3

所以代码里写成：

(weight[x] + rel - weight[y] + 3) % 3

加3是为了防止负数取模出现负值。这是带权并查集最容易写错的地方。每次合并前，先梳理清楚自己定义的关系含义，再套公式，就不会翻车。

find里的权值累加也要注意：路径压缩时，当前节点的父节点已经变成了根节点，所以要用递归先找到父节点的根，再在回溯过程中把父节点的权值累加到当前节点上。这就是为什么递归版find里必须先递归再累加。顺序反了，weight就算错了。

4.4 模运算与方向约定的坑

我在竞赛和实验里见过不少人栽在同一类坑里：关系定义方向没统一。比如你定义1表示x吃y，合并公式里用的却是weight[y] - weight[x]，结果答案全错。改个方向sign，整个程序都要跟着改。最稳妥的办法是，在写unite之前先在白纸上把三种关系画成有向图，标清每条边的权值方向，再对着画好的图写公式。

另一个典型问题是多个关系叠加时忘记对3取模。比如weight[x]一路累加，如果超过了3，必须取模，否则后面所有关系判断都会乱掉。取模的位置，一个在find累加时，一个在unite推导新权重时，这两处缺一不可。

还有一点，食物链问题里经常出现“同一个节点同时给多条矛盾关系”的情况，比如先说明A吃B，又说B吃A。这不是并查集能自动识别的，需要你在合并前先检查关系是否冲突。也就是unite函数里，如果两个节点已经同根，要先做断言校验，校验失败立即返回false。这个分支逻辑不可省略。

5. 实战中的坑：排错与优化技巧

5.1 递归爆栈与迭代写法

基础并查集和带权并查集，我优先推荐递归写法，因为代码短、思路直白。但如果你处理的是超大图，比如几百万个节点在极端数据下构造出一条极长的链，递归find可能会踩爆系统栈。

解决思路有两个。第一是改用按秩合并，保证树高始终维持在O(log n)，递归深度不会太大。第二是写迭代版find，第一次循环找根，第二次循环做路径压缩指向根。带权并查集的迭代版会更麻烦一些，因为你要先记录每个节点原来的父节点，再二次遍历时累加权值，建议新手还是从递归入手，遇到问题再优化。

我个人的习惯是：除非题目明确卡递归栈内存，否则一律写递归。因为带权并查集迭代版出错概率实在太高。

5.2 合并方向搞错的典型症状

如果你发现查询结果时对时不对，大概率是union或者unite合并方向出问题。比如第4节的公式里，parent[ry] = rx是有方向的，如果写成了parent[rx] = ry，那么weight[ry]的推导公式也得跟着镜像翻转。忘了翻转就会产生逻辑错误。

再比如，树a的秩小于树b，你把树a挂到树b下面是对的；如果反过来，并查集本身不会报错，但树高会退化，导致后续查询变慢。这类错误隐蔽性不强，但排查起来没有头绪。

我常用的调试方案是：写一个暴力程序，用真正的二维数组模拟连通关系，然后随机生成操作序列，对比并查集程序的结果。暴力解法虽然慢，但作为金标准非常好用。数据规模不用大，几十个节点跑几百轮就能暴露问题。

5.3 面试中高频出现的并查集变体

除了最基础的连通性问题和Kruskal，还有几个变体值得提前准备。第一个是集合大小统计：在并查集节点上额外维护sz数组，合并时累加，可以快速获取任意集合的大小。

第二个是带删除的并查集。注意，标准并查集是不支持删除一个元素的，因为树结构里如果删掉某个节点，它的子树会变得无家可归。现实需求里“把某个人移出群聊”的场景，通常通过加一个“代理节点”实现：为每个元素建立一个不会删除的外部节点，元素本身挂在这个外部节点下面。删除时，给这个元素重新分配一个新代理节点即可。

第三个是可撤销并查集。它用于带“后悔”操作的问题，需要把每次合并写入栈，路径压缩会破坏可撤销性，所以一般只做按秩合并，不压缩路径。复杂度退化成O(log n)，但仍然实用。

这几个变体，面试里问的频率逐步上升，建议至少理解前两个。

5.4 排查速查表

这些坑，百分之八九十都能用“打印parent中间结果”的方式快速定位。我在调试带权并查集时，会额外打印weight数组，多数情况下几组小数据就能找到问题。

6. 从工程实践到算法学习的几点体会

如果你只是应付考试，把基础并查集手写三遍，再把带权并查集的食物链例题完整推导一遍，基本就不会有问题了。但如果你像我一样在工程里真正用到并查集，会发现它最大的价值不是“快”，而是让代码逻辑变得非常干净。几个不同来源的连通关系，几个相互独立的集合合并，并查集都能用统一接口表达，代码结构一目了然。

有一个小技巧值得分享：写并查集类时，我会把find设计成公共方法，把unite设计成返回bool值的方法。这样上层代码无论是做Kruskal、做闭环检测，还是做关系断言，都能直接复用，不用每次都去判断“先查连通再合并”。这个小接口设计，在很多竞赛模板和工程库里都能看到，说明确实经历了实战检验。

还有个个人习惯：每学一种数据结构，我都喜欢在笔记本上画一张它对应的“状态演化图”。比如并查集合并两个树时，从两个根到新树，每一步都画出来。遇到带权并查集，边上的权值也画出来。图画明白了，公式不用背，代码也不会写错。这个习惯帮我解决过很多看似玄学的bug，推荐你也试试。