定义支持路径压缩与按秩合并的union-find类，用vector parent和rank初始化，find采用递归或迭代路径压缩，unite比较秩以控制树高，connected通过find判断，均摊时间复杂度o(α(n))。

需要在C++程序中高效判断大量节点间的连通性，且要求每次查询接近常数时间、合并操作稳定可靠，同时避免树退化导致性能劣化。

定义并查集基础结构与初始化

声明一个支持路径压缩的Union-Find类，用vector存储父节点索引，下标即为节点编号（0-based）。

构造函数接收节点总数n，将parent[i]初始化为i，表示每个节点初始自成一集。

这一步不能跳过或错写为-1：若初始化为-1，后续find逻辑会因负数索引越界崩溃。

实现带路径压缩的查找操作

方法一：递归实现

定义int find(int x)，若parent[x] != x，则递归调用find(parent[x])并将返回值赋给parent[x]，最后返回parent[x]。

递归版本简洁但深度过大时可能栈溢出，适用于节点总数不超过10⁵且树高可控的场景。

方法二：迭代实现

先用临时容器记录从x到根路径上所有节点；再遍历该路径，将每个节点的parent设为最终根节点。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

【必须确保路径上所有中间节点都更新父指针，否则路径压缩不完整】

实现按秩合并的联合操作

第一步：在类中添加vector rank，初始化全为0。

第二步：定义void unite(int x, int y)，先find(x)和find(y)得到各自根节点rx、ry。

第三步：若rx == ry，直接返回；否则比较rank[rx]与rank[ry]：较小秩的根指向较大秩的根；若相等，则任选其一作为新根，并将其rank加1。

按秩合并能有效控制树高，配合路径压缩使单次操作均摊时间趋近O(α(n))，α为反阿克曼函数。

编写连通性判定与测试主逻辑

添加bool connected(int x, int y)接口，直接返回find(x) == find(y)。

在main函数中创建UnionFind uf(10)，执行uf.unite(0,1)→uf.unite(1,2)→uf.unite(3,4)，然后验证uf.connected(0,2)为true、uf.connected(0,3)为false。

这一步操作起来很简单，直接把文件拖进去就行。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！