并查集通过路径压缩和按秩合并优化，显著提升操作效率。1. 初始化每个元素父节点为自身，秩为0；2. 查找时递归压缩路径，使节点直连根；3. 合并时按秩挂载，小秩并入大秩，相等则任选根并增秩。此结构支持高效集合查询与合并，平均时间接近常数。
在C++中实现并查集（Disjoint Set Union, DSU）时，路径压缩和按秩合并是两个关键优化技术，它们能显著提升查找与合并操作的效率，使平均时间复杂度接近常数级别。
基本结构设计
并查集用于维护一组元素的划分，支持快速查找某个元素所属集合以及合并两个集合。核心是用数组存储每个节点的父节点。
初始化时，每个元素的父节点指向自己，表示独立集合。可以用一个vector保存parent信息，另一个记录每个集合的秩（rank），用于按秩合并。
示例结构：
vector
路径压缩（Path Compression）
在查找根节点的过程中，把沿途的所有节点直接连接到根，从而压平树结构。这样后续查找会更快。
立即学习“C++免费学习笔记（深入）”；
查找函数使用递归实现路径压缩非常简洁：
- 如果当前节点不是根（parent[x] != x），则递归查找根，并将parent[x]更新为返回值
- 最终返回根节点
这一操作让整条路径上的节点都指向根，极大减少未来查找深度。
代码片段：
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
按秩合并（Union by Rank）
合并两个集合时，通过比较两棵树的秩决定挂载方向：将秩较小的树根连到秩较大的树根下。若秩相等，则任选一方作为新根，并将其秩加一。
这样做可以避免生成过深的树，控制整体高度。
- 找到两个元素的根
- 比较对应秩的大小
- 小秩向大秩合并
- 相同秩时更新新根的秩
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx]
parent[rx] = ry;
else if (rank[rx] > rank[ry])
parent[ry] = rx;
else {
parent[ry] = rx;
++rank[rx];
}
}
完整实现示例
封装成类更便于管理。构造函数初始化每个节点为独立集合。
假设处理n个编号从0到n-1的元素：
struct DSU {
vector
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i
}
int find(int x) { ... }
void unite(int x, int y) { ... }
};
这个结构可在Kruskal算法、连通分量判断等场景中高效使用。
基本上就这些。路径压缩配合按秩合并，使得DSU的操作几乎是常数时间，适合大规模数据处理。注意两者结合效果最佳，单独使用任一优化也能带来明显提升。
