并查集通过路径压缩和按秩合并高效处理集合合并与查询，支持连通性判断、求连通分量等操作，常用于Kruskal算法、岛屿问题等场景。
并查集（Union-Find）是一种高效处理不相交集合合并与查询的数据结构，常用于解决连通性问题，比如判断图中两个节点是否连通、求连通分量个数等。在 C++ 中实现并查集非常直观，核心操作包括查找（find）和合并（union）。通过路径压缩和按秩合并优化，可以将时间复杂度接近常数级别。
基本结构与初始化
并查集通常用一个数组 parent 来表示每个元素的父节点，初始时每个元素的父节点是自己，表示各自独立成一个集合。
还可以引入 rank 数组来记录每棵树的“秩”（近似高度），用于优化合并操作。
class UnionFind {public: vector parent; vector rank; // 构造函数，初始化 n 个独立元素 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 unite(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]++; } } // 判断两个元素是否属于同一集合 bool connected(int x, int y) { return find(x) == find(y); }};
关键优化：路径压缩与按秩合并
这两个优化策略显著提升并查集效率：
立即学习“C++免费学习笔记（深入）”；
路径压缩：在 find 过程中，把沿途所有节点直接连到根节点，降低后续查找成本。 按秩合并：合并时尽量让较矮的树接在较高的树下，避免生成过深的树，控制整体高度。
经过这两种优化后，单次操作的平均时间复杂度接近 O(α(n))，其中 α 是阿克曼函数的反函数，增长极慢，可视为常数。
实际应用场景举例
假设要判断无向图中边的连接是否会形成环，可以用并查集逐条处理边：
#include #include using namespace std;int main() { int n = 5; UnionFind uf(n); // 添加边 (0,1), (1,2), (3,4) uf.unite(0, 1); uf.unite(1, 2); uf.unite(3, 4); cout << "0 和 2 连通吗？" << (uf.connected(0, 2) ? "是" : "否") << endl; // 是 cout << "0 和 3 连通吗？" << (uf.connected(0, 3) ? "是" : "否") << endl; // 否 uf.unite(2, 3); cout << "0 和 4 连通了吗？" << (uf.connected(0, 4) ? "是" : "否") << endl; // 是 return 0;}
总结与扩展建议
并查集适合动态维护集合的合并与查询，代码简洁且效率高。在算法竞赛或工程中常用于：
Kruskal 最小生成树算法 岛屿数量问题（替代 DFS/BFS） 社交网络中的好友关系连通判断
可以根据需要扩展支持集合大小统计、删除操作（需更复杂结构）等功能。掌握基础实现后，灵活应用是关键。
基本上就这些。
以上就是C++怎么实现一个并查集算法_C++算法设计与并查集实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1484796.html
微信扫一扫 
支付宝扫一扫 
