一、认识并查集
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. 查询操作
查询某个元素属于哪个集合时,只需找到该元素所在树的根节点。例如,查询 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;
}
}
}
3.2. 查找(带路径压缩)
查找操作的目的是找到根节点。为了提高效率,使用路径压缩技术,将查找路径上的所有节点直接指向根节点。
public int {
(parent[x] != x) {
parent[x] = find(parent[x]);
}
parent[x];
}




