并查集通过路径压缩和按秩合并优化，显著提升操作效率。1. 初始化每个元素父节点为自身，秩为0；2. 查找时递归压缩路径，使节点直连根；3. 合并时按秩挂载，小秩并入大秩，相等则任选根并增秩。此结构支持高效集合查询与合并，平均时间接近常数。
在C++中实现并查集（Disjoint Set Union, DSU）时，路径压缩和按秩合并是两个关键优化技术，它们能显著提升查找与合并操作的效率，使平均时间复杂度接近常数级别。
基本结构设计
并查集用于维护一组元素的划分，支持快速查找某个元素所属集合以及合并两个集合。核心是用数组存储每个节点的父节点。
初始化时，每个元素的父节点指向自己，表示独立集合。可以用一个vector保存parent信息，另一个记录每个集合的秩（rank），用于按秩合并。
示例结构：
vector parent; // 父节点索引 vector rank; // 树的高度上界
路径压缩（Path Compression）
在查找根节点的过程中，把沿途的所有节点直接连接到根，从而压平树结构。这样后续查找会更快。
立即学习“C++免费学习笔记（深入）”；
查找函数使用递归实现路径压缩非常简洁：
如果当前节点不是根（parent[x] != x），则递归查找根，并将parent[x]更新为返回值 最终返回根节点
这一操作让整条路径上的节点都指向根，极大减少未来查找深度。
代码片段：
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
按秩合并（Union by Rank）
合并两个集合时，通过比较两棵树的秩决定挂载方向：将秩较小的树根连到秩较大的树根下。若秩相等，则任选一方作为新根，并将其秩加一。
这样做可以避免生成过深的树，控制整体高度。
找到两个元素的根 比较对应秩的大小 小秩向大秩合并 相同秩时更新新根的秩 合并逻辑：
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] parent[rx] = ry;
else if (rank[rx] > rank[ry])
parent[ry] = rx;
else {
parent[ry] = rx;
++rank[rx];
}
}
完整实现示例
封装成类更便于管理。构造函数初始化每个节点为独立集合。
假设处理n个编号从0到n-1的元素：
struct DSU {
vector parent, rank;
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i }
int find(int x) { … }
void unite(int x, int y) { … }
};
这个结构可在Kruskal算法、连通分量判断等场景中高效使用。
基本上就这些。路径压缩配合按秩合并，使得DSU的操作几乎是常数时间，适合大规模数据处理。注意两者结合效果最佳，单独使用任一优化也能带来明显提升。
以上就是C++怎么实现一个并查集_C++数据结构中Disjoint Set Union的路径压缩与按秩合并的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485207.html
微信扫一扫 
支付宝扫一扫 
