并查集通过父节点数组实现，初始化时每个节点指向自己，find函数递归查找根节点并进行路径压缩，降低树高以提升效率，配合按秩合并可接近O(1)操作。
在C++中实现并查集（Disjoint Set Union, DSU）的查找操作，核心是通过数组记录每个节点的父节点，并使用路径压缩优化查找效率。
基本结构定义
并查集通常用一个vector或数组来维护每个元素的父节点。初始化时，每个元素的父节点指向自己，表示各自为独立集合。
示例代码：
#include
using namespace std;vector parent;// 初始化：每个节点的父节点是自己void init(int n) { parent.resize(n); for (int i = 0; i < n; ++i) { parent[i] = i; }}
查找函数实现
find 函数用于查找某个元素所在集合的根节点（代表元）。通过递归方式向上查找，并在回溯时将沿途节点直接挂到根节点下，实现路径压缩。
标准查找方法：
int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 路径压缩 } return parent[x];}
路径压缩的作用是降低树的高度，使后续查找接近 O(1) 时间复杂度。
立即学习“C++免费学习笔记（深入）”；
按秩合并优化（可选）
为了进一步提升性能，可以引入秩（rank）数组，在合并时将低秩树接到高秩树上，避免退化成链。
vector rank;void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { if (rank[rootX] rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } }}
使用示例
完整的小例子演示如何初始化、查找和合并：
#include #include using namespace std;vector parent, rank;void init(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 rx = find(x), ry = find(y); if (rx == ry) return; if (rank[rx] rank[ry]) parent[ry] = rx; else { parent[ry] = rx; rank[rx]++; }}int main() { init(5); unite(0, 1); unite(1, 2); cout << "Find(0): " << find(0) << endl; // 输出根节点 cout << "Find(2): " << find(2) << endl; // 应与find(0)相同 return 0;}
基本上就这些。查找的核心是递归加路径压缩，配合按秩合并能保证高效操作。
以上就是c++++中如何实现并查集的查找_c++并查集查找方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1477210.html
微信扫一扫 
支付宝扫一扫 
