并查集通过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[rootX] = rootY; } else 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 决定谁作为新根，避免树退化为链表
路径压缩与按秩合并的作用
这两个优化能显著提升效率：
白月生产企业订单管理系统GBK2.0 Build 080807
下载
请注意以下说明:1、本程序允许任何人免费使用。2、本程序采用PHP+MYSQL架构编写。并且经过ZEND加密，所以运行环境需要有ZEND引擎支持。3、需要售后服务的，请与本作者联系，联系方式见下方。4、本程序还可以与您的网站想整合，可以实现用户在线服务功能，可以让客户管理自己的信息，可以查询自己的订单状况。以及返点信息等相关客户利益的信息。这个功能可提高客户的向心度。安装方法：1、解压本系统，放在
立即学习“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 优化，但建议默认加上以保证性能稳定。
