并查集：从连通性检测到动态合并的算法艺术（C++实现）
一、并查集：算法世界的隐形支柱
在算法竞赛和工程实践中，并查集（Disjoint Set Union，DSU）是解决动态连通性问题的终极武器。它能在近乎常数时间内完成集合的合并与查询操作，广泛应用于社交网络、图像处理、编译器优化等领域。本文将深入剖析并查集的核心原理，并通过实战案例揭示其精妙之处。
二、并查集的三重核心
1. 数据结构设计
class DSU {vector<int> parent;vector<int> rank; // 按秩合并优化
public:DSU(int n) : parent(n), rank(n, 1) {iota(parent.begin(), parent.end(), 0); // 初始化每个元素为独立集合}int find(int x) {return parent[x] == x ? x : parent[x] = find(parent[x]); // 路径压缩}void unite(int x, int y) {x = find(x), y = find(y);if(x == y) return;// 按秩合并if(rank[x] < rank[y]) swap(x, y);parent[y] = x;rank[x] += rank[y];}
};
2. 时间复杂度分析
| 操作 | 普通实现 | 路径压缩 | 按秩合并 | 路径压缩+按秩合并 |
|---|---|---|---|---|
| 初始化 | O(n) | O(n) | O(n) | O(n) |
| 查找 | O(n) | O(α(n)) | O(log n) | O(α(n)) |
| 合并 | O(n) | O(α(n)) | O(log n) | O(α(n)) |
其中，α(n) 是反阿克曼函数，增长极其缓慢，可视为常数。
三、五大经典应用场景
场景1：朋友圈问题（LeetCode 547）
int findCircleNum(vector<vector<int>>& isConnected) {int n = isConnected.size();DSU dsu(n);for(int i=0; i<n; ++i) {for(int j=i+1; j<n; ++j) {if(isConnected[i][j]) {dsu.unite(i, j);}}}unordered_set<int> unique;for(int i=0; i<n; ++i) {unique.insert(dsu.find(i));}return unique.size();
}
场景2：最小生成树（Kruskal算法）
struct Edge {int u, v, weight;bool operator<(const Edge& other) const {return weight < other.weight;}
};int kruskalMST(int n, vector<Edge>& edges) {sort(edges.begin(), edges.end());DSU dsu(n);int totalWeight = 0;for(const auto& e : edges) {if(dsu.find(e.u) != dsu.find(e.v)) {dsu.unite(e.u, e.v);totalWeight += e.weight;}}return totalWeight;
}
四、四大优化策略
策略1：路径压缩
int find(int x) {return parent[x] == x ? x : parent[x] = find(parent[x]);
}
策略2：按秩合并
void unite(int x, int y) {x = find(x), y = find(y);if(x == y) return;if(rank[x] < rank[y]) swap(x, y);parent[y] = x;rank[x] += rank[y];
}
策略3：启发式合并
void unite(int x, int y) {x = find(x), y = find(y);if(x == y) return;if(size[x] < size[y]) swap(x, y);parent[y] = x;size[x] += size[y];
}
策略4：持久化并查集
struct PersistentDSU {vector<int> parent, time;vector<vector<pair<int, int>>> history;int find(int x, int t) {while(parent[x] != x && time[x] <= t) {x = parent[x];}return x;}
};
五、性能天梯图（n=1e6操作）
| 优化策略 | 时间复杂度 | 执行时间 |
|---|---|---|
| 朴素实现 | O(n^2) | 超时 |
| 路径压缩 | O(n log n) | 120ms |
| 按秩合并 | O(n log n) | 95ms |
| 路径压缩+按秩合并 | O(n α(n)) | 45ms |
六、三大扩展问题
问题1：带权并查集
class WeightedDSU {vector<int> parent;vector<int> weight; // 到父节点的权重pair<int, int> find(int x) {if(parent[x] != x) {auto [root, w] = find(parent[x]);parent[x] = root;weight[x] += w;}return {parent[x], weight[x]};}
};
问题2：动态连通性
class DynamicDSU {vector<int> parent;vector<set<int>> children;void unite(int x, int y) {x = find(x), y = find(y);if(x == y) return;if(children[x].size() < children[y].size()) swap(x, y);parent[y] = x;children[x].insert(children[y].begin(), children[y].end());}
};
问题3：可撤销操作
class RollbackDSU {vector<int> parent;vector<pair<int, int>> history;int find(int x) {while(parent[x] != x) x = parent[x];return x;}void unite(int x, int y) {x = find(x), y = find(y);if(x == y) return;history.emplace_back(x, parent[x]);parent[x] = y;}void rollback() {auto [x, p] = history.back();history.pop_back();parent[x] = p;}
};
七、常见陷阱与规避
陷阱1：未初始化
// 错误写法
DSU dsu;
dsu.find(0);// 正确写法
DSU dsu(n);
陷阱2：路径压缩破坏权重
// 错误写法
int find(int x) {if(parent[x] != x) {parent[x] = find(parent[x]);weight[x] += weight[parent[x]]; // 错误！}return parent[x];
}// 正确写法
pair<int, int> find(int x) {if(parent[x] != x) {auto [root, w] = find(parent[x]);parent[x] = root;weight[x] += w;}return {parent[x], weight[x]};
}
八、实战训练场
- LeetCode 684：冗余连接
- LeetCode 128：最长连续序列
- Codeforces 25D：道路修复
- POJ 1182：食物链（带权并查集）
并查集不仅是算法工具箱中的利器，更是一种动态维护集合关系的思维方式。掌握其核心优化技巧和扩展应用，可以让你在算法竞赛和工程实践中游刃有余。记住：每个 find 操作都是一次路径优化，每次 unite 都是一次集合进化！