一、认识并查集
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];
}
