企业官网建设流程全解析

1. 从“怎么判断两个点连不连”说起

如果你刷过图论题、写过最小生成树，或者参加过任何一场像样的算法面试，大概率遇到过这种需求：给你一堆节点，某些节点之间存在连接关系，然后反复询问“A和B在不在同一个连通块里”，或者动态地往图里加边，同时随时想知道当前的连通分量有几个。

最朴素的做法是建图跑 BFS/DFS，每问一次就遍历一遍。图一大了，查询一多，立刻爆炸。并查集就是专门解决这类动态连通性问题的数据结构，核心思想一句话就能讲完：用一棵树来表示一个集合，树根就是集合的代表元。查两个元素是否同集合，就查它们的根是否相同；合并两个集合，就把一棵树的根接到另一棵树的根下面。

我第一次见这个结构时觉得它“简陋得不像话”——一个数组就能搞定所有事。但正是这个几乎不需要额外空间的数组解法，能把连通性问题的复杂度压到近乎常数级别。工作之后处理一些离线批量任务、合并分组的问题，也经常回来用这套思路。这篇文章不绕弯子，直接把这东西讲透：概念、代码、典型习题，按我实际学习和刷题的经验来。

适合看这篇文章的人挺明确的：准备算法面试的、打竞赛的、或者工作中遇到“分组合并”“连通性判断”场景的开发者。基础要求不高，看得懂数组和递归就行。看完你能收获三样东西：并查集的完整原理、一套可以直接抄的模板代码、还有几道从易到难的经典题及解题套路。

2. 核心概念：一个数组如何表达集合关系

2.1 树的表示法与“老大”思想

并查集内部只维护一个数组，通常叫 parent 或 fa。parent[i] 表示节点 i 的父节点。如果 parent[i] = i，说明 i 就是它所在树的根。

这里有个容易绕弯的地方：并查集里的树和普通二叉树完全不同。它不关心节点的左右孩子，只关心“谁指向谁”。每个节点只有一个父指针，顺着父指针一直往上爬，总能到达根节点。根节点是集合的“代言人”，我们叫它代表元。

可以这样记忆：每个集合就是一个帮派，根是帮主，其他人一层层往上汇报。判断两个人是不是一伙的，不需要知道帮派里所有人的名字，只需要看他们最终汇报到的是不是同一个帮主。

初始化时，每个节点都是孤立的一棵树，parent[i] = i。此时有 n 个集合。每次合并，树的个数减一。所以如果想统计连通块数，维护一个变量记录树根数量即可，初始为 n，每次成功合并就减一。

2.2 两个核心操作：Find 与 Union

一切并查集的变体，本质都是围绕这两个函数做优化和扩展。

Find 操作输入一个节点，输出它所在树的根。实现就是顺着 parent 不断往上跳，直到某个节点的父节点是它自己：

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

Union 操作输入两个节点，把二者所在集合合并。标准做法是分别找到它们的根，然后把其中一个根接到另一个根下面：

void unionSet(int a, int b) { int ra = find(a); int rb = find(b); if (ra != rb) { parent[ra] = rb; // 把 a 的根接到 b 的根下面 } }

这里注意一个细节：Union 成功与否取决于两个元素是否已在同一集合。如果 ra == rb，说明本来就在一起，此时什么都不用做。很多新手在写带“集合数量”的题目时，这里忘了判断，导致数量统计出错。

3. 代码实现的三个台阶：从能跑到跑得快

3.1 基础版代码与它的性能瓶颈

先给一份完整的入门模板，这个版本是后面所有优化版本的底座。我用 C++ 来写，换成别的语言思路完全一致：

#include <vector> using namespace std; class DSU { public: vector<int> parent; DSU(int n) { parent.resize(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 unionSet(int a, int b) { int ra = find(a); int rb = find(b); if (ra != rb) { parent[ra] = rb; } } bool isConnected(int a, int b) { return find(a) == find(b); } };

这个版本能正确工作，但性能是个隐患。如果合并时总把深的树接到浅的树上，树会变得越来越深。最坏情况下，n 次操作的时间复杂度退化成 O(n²)。注意，树深不等于节点数，但它会随着“畸形合并”不断恶化。

可以想象一个极端场景：每次 unionSet(0, 1)、unionSet(0, 2)、unionSet(0, 3)…… 每次都把新节点接到 0 下面，树就成了一条长链，find 最坏要走 n 步。如果随后有 m 次查询，总代价就是 O(n*m)。

3.2 路径压缩：让树变平的魔法

路径压缩的思路特别朴素：既然 find 过程中已经遍历了从节点到根的整条路径，那顺便把路径上所有节点的父指针直接指向根，下次再查就是 O(1)。

这是递归写法，代码比循环版短不少：

int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; }

递归版的好处不只是短。它在回溯过程中自底向上把整条链全部扁平化，写起来几乎不可能出错。我第一次学并查集时用的就是递归版，至今没因为递归调用出过问题。

有个坑要提醒：递归深度。如果系统栈较小（比如 Windows 下某些环境默认只有 1MB 栈空间），遇到一条 n = 10^6 的长链，递归 find 可能直接栈溢出。不过路径压缩本身会让长链快速消失，但第一次 find 时仍然会深入递归到底。你需要评估自己的数据规模和环境。竞赛里一般没事，但如果是嵌入式环境或者某些限制栈大小的线上测评系统，建议用非递归版并配合下面说的按秩合并，双保险。

非递归版路径压缩稍麻烦一点，需要先找到根，再走一遍把路径上的节点都改成指向根：

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; }

3.3 按秩合并：用树的高度做平衡

路径压缩只管把树拉平，但如果不做压缩（有些场景需要保留树结构），树还是会退化成链。按秩合并就是另一个维度的优化：合并时，把高度较小的树接到高度较大的树下面，避免树长高。

术语说明：“秩”可以是子树高度，也可以是子树大小。我用 size 来合并，统计信息容易维护，效果也完全够好：

class DSU { public: vector<int> parent; vector<int> size; DSU(int n) { parent.resize(n); size.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]; } void unionSet(int a, int b) { int ra = find(a); int rb = find(b); if (ra == rb) return; // 把小的树接到大的树下面 if (size[ra] < size[rb]) { swap(ra, rb); } parent[rb] = ra; size[ra] += size[rb]; } };

为什么按秩合并有用？因为树的高度直接决定了 find 的代价。每次合并都把更矮的树挂到更高的树下，树高增长的速度被控制在 log 级别。配合路径压缩后，单次操作均摊复杂度反超阿克曼函数的反函数——也就是实际可以当作常数看待。面试时如果被问到“并查集为什么快”，能说出“路径压缩 + 按秩合并 → O(α(n)) 均摊”这句话就够了。

在我实际使用中，路径压缩 + 按大小合并的组合最稳。单独用路径压缩，某些极端数据下虽然也能过，但稳一点总没坏处。而且 size 数组后续还能用来计算集合大小，解题时经常用得上，属于“一个数组两种用途”。

3.4 一个功能完整的模板封装

把上面这些整合起来，给出我平时直接复制用的模板。这个版本支持：初始化、查找根、合并、判断连通、查询集合大小，还顺便统计了集合个数：

#include <vector> using namespace std; class DSU { private: vector<int> parent, sz; public: int components; // 当前连通分量个数 DSU(int n) { parent.resize(n); sz.resize(n, 1); for (int i = 0; i < n; i++) parent[i] = i; components = n; } int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; // 路径压缩的迭代写法 x = parent[x]; } return x; } bool unionSet(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]; components--; return true; // 合并成功 } bool isConnected(int a, int b) { return find(a) == find(b); } int sizeOf(int x) { return sz[find(x)]; } };

这里的 find 用了一种叫“路径分裂”的迭代写法：parent[x] = parent[parent[x]]，每步把当前节点的父指针往爷爷方向挪一格。效果类似路径压缩，但代码更短，也没有递归。实测性能很好，推荐日常使用。

4. 习题拆解：从裸模板到思维进阶

只讲概念不刷题等于白看。我按难度梯度挑了四道典型题，每道题对应一类常见的应用场景。代码都给出，你可以直接照着写完再去扩展。

4.1 入门模板题：计算连通分量数量

问题描述：给定 n 个节点（编号 0 到 n-1）和 m 条边，每条边连接两个节点，求最终有多少个连通块。

这道题就是模板的直用。核心逻辑是维护 components 变量，初始为 n，每次 union 成功就减一。等所有边处理完，components 的值就是答案。

完整解法：

#include <iostream> using namespace std; class DSU { /* 按上面封装，此处省略重复代码 */ }; int main() { int n, m; cin >> n >> m; DSU dsu(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; dsu.unionSet(u, v); } cout << dsu.components << endl; return 0; }

这个题的意义在于让你验证模板有没有写错。注意一个细节：如果图中有重边，union 会返回 false，components 不会重复减一，这是对的。比如两个点之间有三条边，连通块数仍然只减一次。

4.2 判环：图里有没有“绕回来的路”

问题描述：给定 n 个节点和 m 条边，判断这张图是否存在环（假设初始时没有自环）。

判环思路：在加边的过程中，如果发现两个节点已经在同一个集合里，说明它们之间已经有一条路径连通，此时再加一条边就会形成环。这个场景秒杀一切“无向图判环”的题。

bool hasCycle(int n, vector<pair<int,int>>& edges) { DSU dsu(n); for (auto& e : edges) { int u = e.first, v = e.second; if (dsu.isConnected(u, v)) { return true; // 本来就连通，再加边成环 } dsu.unionSet(u, v); } return false; }

判环是并查集最经典的“反直觉”应用。表面上看它和连通性无关，但利用了“连通块内任意两点间必有路径，再加边必成环”这个性质。面试题经常包装成“给你一堆朋友关系，判断是否存在矛盾”——本质上一模一样。

4.3 带权并查集：不只是连不连，还要知道“相差多少”

这是把并查集从“静态连通”推向“动态关系”的关键一步。问题背景：有 n 个变量，给出若干条约束“X 比 Y 大 k”，问这些约束之间是否存在矛盾。

核心思想：在原来只记录父子关系的 parent 数组之外，额外开一个 dist 数组，记录当前节点到父节点的权值差。find 递归返回时，需要同步更新 dist：

int find(int x) { if (parent[x] != x) { int origin = parent[x]; parent[x] = find(parent[x]); dist[x] += dist[origin]; } return parent[x]; } void unionSet(int a, int b, int w) { // 含义：a 比 b 大 w int ra = find(a); int rb = find(b); if (ra == rb) { // 检查是否矛盾：dist[a] - dist[b] 应该等于 w // 若不符则存在矛盾 return; } parent[ra] = rb; // 数学推导：dist[a] + dist[ra] = w + dist[b] dist[ra] = dist[b] + w - dist[a]; }

那个 dist[ra] = dist[b] + w - dist[a] 的公式，很多初学者直接背，但我觉得还是理解一下比较好。设节点 a 到 ra 的距离是 dist[a]，节点 b 到 rb 的距离是 dist[b]。将 ra 挂到 rb 下后，新 root 是 rb，要保证从 a 到 rb 的总距离满足约束。画出向量图：dist[a] + dist[ra] = w + dist[b]，移项就得到上述公式。这种“带权”模式可以扩展到很多“相对关系”的题目：食物链、敌人朋友、区间和校验等，统统是这个套路。

4.4 拓展：离线处理区间查询

有一类题目长得完全不像并查集，需要绕个弯才能想到。比如：给定 n 个点和 m 个询问，每次询问“区间 [l, r] 内的点是否全部连通”，允许离线处理。

这种题有个经典做法：把所有询问按右端点从小到大排序，然后从 1 到 n 逐渐加点。维护一个数组 last[i]，表示 i 左边最近的、和 i 不在同一连通块内的位置。这个思路初看绕，但本质上利用了并查集的「逐步加边」能力。

这个场景在面试题里相对少见，更多出现在竞赛。我的建议是：先把前三种吃透，这种离线技巧作为进阶方向，等你遇到具体题再回来翻思路。

5. 常见问题与调试实录

5.1 无限递归或栈溢出

现象：find 写成了递归，在大数据上爆栈。

原因：路径压缩未生效，或者是合并策略导致树过深。解决办法：

• 改用非递归 find（路径分裂写法）；
• 检查 unionSet 时是否真的把矮树接高树；
• 确保查根时调用的都是 find 而不是直接访问 parent。

实战教训：有一次在某个在线测评平台跑 10^6 级别的链式合并，递归 find 直接段错误。换成迭代版一次通过。如果你的评测环境不可控，优先用迭代版。

5.2 集合数量统计错误

现象：components 反复减一，最终结果偏小。

原因：unionSet 里没有判断 ra == rb 就执行了减一。

void unionSet(int a, int b) { int ra = find(a); int rb = find(b); if (ra == rb) return; // 这里缺少这行 parent[ra] = rb; components--; }

加一行判断就解决。调试时可以在 unionSet 里打日志，看看哪些边实际上没被合并。

5.3 带权并查集的 dist 更新遗漏

现象：在 find 路径压缩时不更新 dist，导致后续查询距离错误。

正确写法是每次修改父节点时，同步累加 dist。因为路径压缩会让节点直接指向 root，原来的父节点路径上的距离必须“合并”到新距离中。

我在第一次写带权并查集时最容易漏的点：写 find 时只记得 parent[x] = find(parent[x]); 忘记 dist[x] += dist[原parent]。写完过样例，一提交就错。排查半天发现是这个问题。

5.4 一个快速排查表

6. 实用心得

6.1 并查集的高级变体——「域压缩」思想

如果你刷题刷得比较深，会遇到一类“朋友敌人”问题（比如经典的食物链），用同一个并查集维护多个相对关系。这类题的通用解法叫“域扩张”：把每个元素拆成多个逻辑节点，分别代表不同的关系状态。

思路是用 3n 个节点的并查集：i 表示自身，i+n 表示 i 的天敌，i+2n 表示 i 的猎物。合并关系时，同时维护三组约束。这种扩展方式能应对非常复杂的关系描述，关键在于想清楚“拆成几个域”和“域之间的约束关系”。

这也是带权并查集趋于复杂时，一个常被推荐的做法。

6.2 一个冷门但好用的方向：并查集维护图连通性

在线加边、删边问题不好做，但如果不是动态删边，而是“倒过来”执行操作——先把所有边全部加上，再逆着操作顺序逐个删边，就等价于“倒着加边”，并查集天然支持加边，于是问题迎刃而解。

这个离线技巧在很多竞赛题里是核心突破口。我遇到最典型的一题：给了一堆操作，每个操作可能删掉一条边，然后查询两个点是否连通。正着做要处理删除，很麻烦；倒着做就变成“加边 + 查询连通”，甚至比正着做还直观。

6.3 最后再分享一个写模板的小技巧

我写并查集有一点习惯：unionSet 返回 bool，用来告诉调用者合并是否真的成功。这样在外面写逻辑时，代码更干净。比如 Kruskal 最小生成树算法里，就需要判断每条边“要不要收进来”——如果 unionSet 返回 false，说明这条边会成环，直接跳过。这种返回值设计让并查集不仅仅是“数据结构”，更像是“图的可持久化连接器”，用起来很顺手。

把模板练到闭眼能写，接下来看到任何“分组合并”类的问题，都会条件反射地想到并查集。