认识并查集
并查集（Disjoint Set）是一种用于管理不相交集合的数据结构，核心在于高效处理动态的集合合并与查询操作。它主要支持两个基本功能：
- Find（查找）：确定某个元素属于哪一个集合。
- Union（合并）：将两个元素所在的集合合并为一个集合。
核心原理
集合表示
并查集通常通过一个数组（parent 数组）来表示每个元素的父节点，从而形成森林结构。每个集合用一棵树表示，树的根节点即为该集合的代表元素。初始状态下，每个元素都是一个独立的集合，父节点指向自己。
例如，有 5 个元素（0 到 4），初始 parent 数组为 [0, 1, 2, 3, 4]。
优化技巧
为了提升效率，实际应用中通常会结合两种优化策略：
- 路径压缩：在查找操作中，将查找路径上的所有节点直接指向根节点，减少后续查找的深度。
- 按秩合并：在合并操作中，总是将秩（树的高度或深度）较小的树合并到秩较大的树上，避免树变得过高。
完整代码示例
下面是一个包含路径压缩和按秩合并优化的 Java 实现。初始化时每个元素父节点指向自身，查找时递归更新父节点，合并时比较秩的大小决定连接方向。
public class UnionFind {
private int[] parent;
private int[] rank;
// 初始化并查集
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// 查找操作，带路径压缩
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并操作，带按秩合并
{
find(x);
find(y);
(rootX != rootY) {
(rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} {
parent[rootY] = rootX;
rank[rootX] += ;
}
}
}
{
find(x) == find(y);
}
}
