并查集通过find和merge操作管理集合合并与查询，使用路径压缩和按秩合并优化效率。初始化parent数组使每个节点指向自身，rank记录树高；find递归查找根并压缩路径，merge比较rank决定合并方向，避免退化为链表；二者结合使操作均摊复杂度接近O(α(n))。示例中创建5元素并查集，依次合并0-1-2和3-4，验证连通性后合并两组，最终0与4连通。
在C++中实现并查集的合并操作，核心是通过“按秩合并”或“路径压缩”优化来高效地管理集合的连接关系。并查集（Union-Find Set）常用于处理不相交集合的合并与查询问题，比如判断两个元素是否属于同一集合、动态连通性问题等。
并查集的基本结构
并查集通常用一个数组 parent[] 来表示每个节点的父节点，初始时每个节点的父节点指向自己。另外可以使用 rank[] 数组记录每棵树的“秩”（近似高度），用于优化合并策略。
示例代码结构：
#include #include using namespace std;class UnionFind {private: vector parent; vector rank;public: UnionFind(int n) { parent.resize(n); rank.resize(n, 0); 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 merge(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; // 已在同一集合 // 按秩合并：将低秩树接到高秩树下 if (rank[rootX] rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; // 秩相同，合并后根的秩加1 } } // 判断是否在同一集合 bool connected(int x, int y) { return find(x) == find(y); }};
合并操作的关键点
merge 函数是并查集中实现集合合并的核心方法：
先通过 find 找到两个元素所在集合的根节点 如果根相同，说明已在同一集合，无需合并 否则根据 rank 决定谁作为新根，避免树退化为链表
路径压缩与按秩合并的作用
这两个优化能显著提升效率：
立即学习“C++免费学习笔记（深入）”；
路径压缩让 find 在递归返回时把沿途节点直接连到根上，降低后续查询成本 按秩合并确保较矮的树接到较高的树下，控制整体深度 两者结合后，单次操作的平均时间复杂度接近 O(α(n))，其中 α 是阿克曼函数的反函数，增长极慢
使用示例
下面是一个简单调用示例：
int main() { UnionFind uf(5); // 创建5个元素的并查集 uf.merge(0, 1); uf.merge(1, 2); uf.merge(3, 4); cout << uf.connected(0, 2) << endl; // 输出 1（true） cout << uf.connected(0, 3) << endl; // 输出 0（false） uf.merge(2, 3); cout << uf.connected(0, 4) << endl; // 输出 1（true） return 0;}
基本上就这些。掌握 find 和 merge 的写法，加上路径压缩和按秩合并，就能写出高效的并查集。实际应用中根据题目需求选择是否使用 rank 优化，但建议默认加上以保证性能稳定。
以上就是c++++中如何实现并查集的合并_c++并查集合并方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1477843.html
微信扫一扫 
支付宝扫一扫 
