第36讲 并查集进阶：优化、应用与带权并查集
各位同学，今天我们来聊聊并查集的进阶内容。如果你已经掌握了基础并查集——就是那个能快速判断两个元素是否在同一集合里的数据结构——那这一讲会让你看到它的真正威力。
说实话，基础并查集在实际工程中几乎没法直接用。为什么？因为不加优化的并查集，最坏情况下会退化成一条链，查找效率直接掉到O(n)。我早年在一个图算法项目里就吃过这个亏，数据量一上来，程序直接卡死。从那以后，我养成了一个习惯：写并查集必加优化。
一、路径压缩：让树变矮
先看第一个优化——路径压缩。它的核心思想很简单：在查找某个元素的根节点时，顺便把沿途所有节点直接挂到根节点下面。
你想想看，如果我们每次查找都做一次压缩，那树的深度就会越来越小。理想情况下，几乎所有的节点都直接指向根节点，查找复杂度接近O(1)。
核心代码：
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}这段代码我用了很多年，几乎没变过。注意看，递归调用时我们把父节点更新为根节点。这样下次再查这个节点，一步就能到位。
小技巧：如果你担心递归深度过大，也可以用迭代方式实现路径压缩。不过我个人习惯用递归，代码更简洁，而且实际测试中性能差异不大。
二、按秩合并：让树更平衡
路径压缩解决了查找效率问题，但还有一个问题：合并时如果不加控制，可能会把大树挂到小树下面，导致树变深。
按秩合并就是来解决这个问题的。这里的「秩」通常指树的高度，或者节点数量。合并时，我们总是把秩小的树挂到秩大的树下面。
核心代码：
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}这里我用的是按高度合并。还有一种做法是按大小合并，就是根据集合元素数量来决定谁挂谁。两种都可以，我个人更常用按高度合并，因为它的理论保证更严格——树的高度不会超过log₂n。
注意：如果用了路径压缩，rank值就不再是精确的树高了，而是一个上界估计。但这不影响正确性，我们只需要一个相对大小来判断谁挂谁。
三、并查集的应用：连通分量
好了，优化讲完了。接下来看看并查集能干什么。
第一个经典应用：统计无向图中的连通分量个数。说白了，就是图里有几个「孤岛」。
做法很简单：遍历所有边，对每条边的两个端点执行合并操作。最后统计有多少个节点的父节点是自己，这个数量就是连通分量数。
int countComponents(int n, int** edges, int edgesSize) {
init(n); // 初始化并查集
for (int i = 0; i < edgesSize; i++) {
unionSets(edges[i][0], edges[i][1]);
}
int count = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == i) count++;
}
return count;
}我在一个社交网络分析项目里用过这个思路。当时要快速判断用户群体是否分裂成了多个独立社区，用并查集几毫秒就出结果了。
四、最小生成树Kruskal算法
第二个重要应用：Kruskal算法求最小生成树。这个算法是并查集的「高光时刻」之一。
算法思路其实很直白：
- 把所有边按权重从小到大排序
- 依次取出每条边，如果两个端点不在同一集合，就合并，并把这条边加入生成树
- 重复直到选了n-1条边
为什么用并查集？因为我们需要快速判断一条边的两个端点是否已经连通。如果已经连通，再加这条边就会形成环。
Kruskal核心代码片段：
int kruskal(int n, Edge* edges, int edgeCount) {
// 按权重排序
qsort(edges, edgeCount, sizeof(Edge), cmp);
init(n);
int mstWeight = 0;
int edgeUsed = 0;
for (int i = 0; i < edgeCount && edgeUsed < n-1; i++) {
int u = edges[i].u;
int v = edges[i].v;
if (find(u) != find(v)) {
unionSets(u, v);
mstWeight += edges[i].w;
edgeUsed++;
}
}
return mstWeight;
}我曾经在一个网络布线项目里用Kruskal算法来规划光纤铺设路径。数据量大概有10万个节点，加上路径压缩和按秩合并，跑起来非常快。
五、带权并查集：不止是连通性
基础并查集只告诉我们两个元素是否连通。但有时候，我们还需要知道它们之间的「关系」——比如距离、差值、相对大小等。这时候就需要带权并查集了。
带权并查集的核心思想：每个节点除了记录父节点，还记录一个权值，表示该节点到父节点的某种关系。
举个例子，假设我们要维护一组变量之间的差值关系：x - y = d。我们可以用带权并查集来存储每个变量相对于根节点的差值。
带权并查集查找（带路径压缩）：
int find(int x) {
if (parent[x] != x) {
int originalParent = parent[x];
parent[x] = find(parent[x]);
weight[x] += weight[originalParent]; // 更新权值
}
return parent[x];
}注意看，路径压缩时，权值也要跟着更新。因为节点直接挂到根节点后，它到根节点的权值等于原来到父节点的权值加上父节点到根节点的权值。
合并操作也要考虑权值关系：
bool unionSets(int x, int y, int diff) {
// 假设我们要维护 x - y = diff
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
// 检查是否与已有关系冲突
return (weight[x] - weight[y]) == diff;
}
// 将rootX挂到rootY下
parent[rootX] = rootY;
// 计算rootX到rootY的权值
weight[rootX] = weight[y] + diff - weight[x];
return true;
}避坑指南：我曾经在实现带权并查集时，忘记在路径压缩时更新权值，结果查出来的关系全是错的。调试了整整一个下午才发现问题。所以记住：路径压缩和权值更新必须同步进行。
六、知识体系总览
下面这张图总结了本章的核心内容，你可以把它当作一个快速索引：
七、总结与思考
这一讲我们覆盖了三个核心内容：
- 优化：路径压缩和按秩合并，让并查集真正实用
- 应用：连通分量统计和Kruskal算法，展示了并查集在图和网络问题中的价值
- 带权并查集：在连通性基础上增加了关系维护能力，适用场景更广
说实话，并查集是我个人非常喜欢的一个数据结构。它代码量不大，但思想很巧妙。而且在实际工程中，它的出场率远比你想象的高——从网络连通性检测到数据库的等价类划分，到处都有它的身影。
嗯，这一讲就到这里。代码示例我都贴出来了，建议你亲手敲一遍，特别是带权并查集那部分，自己跑一遍才能体会到路径压缩时权值更新的微妙之处。