一、认识并查集
1. 并查集的定义
并查集(Disjoint Set)是一种用于管理不相交集合的数据结构。它主要用于处理需要动态维护集合合并和查询的问题。核心功能高效支持两个基本操作:
- Find(查找):确定某个元素属于哪一个集合。
- Union(合并):将两个元素所在的集合合并为一个集合。
2. 基本概念
2.1 集合的表示
并查集通常通过一个数组(parent 数组)来表示每个元素的父节点,从而形成森林结构。每个集合用一棵树表示,树的根节点即为该集合的代表元素。
例如,假设有 5 个元素(0, 1, 2, 3, 4),初始时每个元素都是一个独立的集合:
0 1 2 3 4
对应的 parent 数组为 [0, 1, 2, 3, 4],每个元素的父节点指向自己。
2.2 合并操作
当需要将两个元素所在的集合合并时,可以将一个集合的根节点指向另一个集合的根节点。例如,将元素 1 和元素 0 所在的集合合并:
此时 parent 数组变为 [1, 1, 2, 3, 4]。元素 1 和 0 属于同一个集合,根节点是 1。
2.3 查询操作
查询某个元素属于哪个集合时,只需找到该元素所在树的根节点。例如,查询元素 0 属于哪个集合:find(0) 会沿着父节点向上直到根节点。
3. 基本操作实现
3.1 初始化
初始化时,每个元素的父节点指向自己,秩(rank)初始化为 0。
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; // 每个元素的秩初始化为 0
}
}
}
3.2 查找(带路径压缩)
查找操作的目的是找到根节点。为了提高效率,使用路径压缩技术,即将查找路径上的所有节点直接指向根节点。


