并查集算法（Disjoint Set Union，简称DSU）是一种用于处理集合合并和查询的数据结构和算法。它主要用于解决集合的不相交性和合并操作。
在并查集中，每个元素都属于一个集合，并且每个集合有一个代表元素，通常是集合中的某个特定元素。并查集的基本操作包括：
- 初始化： 将每个元素单独放在一个集合中，每个集合的代表元素就是该元素本身。
- 查找（Find）： 查找元素所属的集合，通常通过查找其代表元素来实现。这个操作通常被优化，使得查找路径尽可能短，以提高效率。
- 合并（Union）： 将两个集合合并为一个集合，通常选择其中一个集合的代表元素作为新集合的代表元素，并更新其他元素的归属关系。
并查集通常用于解决一些离散数学中的问题，例如：
- 连通性问题：判断两个元素是否属于同一个集合，即是否连通。
- 最小生成树算法（如Kruskal算法）：按权重递增的顺序选择边，并通过并查集来检测是否形成了环。
- 社交网络中的关系处理：如朋友圈的合并与查询。
以下是并查集（Disjoint Set Union）算法的Java实现，包括详细的注释解释：
import java.util.*;
class DisjointSet {
private int[] parent; // 存储每个节点的父节点
private int[] rank; // 存储每个节点的秩（用于优化）
// 初始化并查集，每个节点都是独立的集合，父节点为自己，秩初始化为1
public DisjointSet(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
// 查找节点的根节点（代表元素）
private int find(int x) {
// 如果当前节点不是根节点，则递归向上找到根节点，并进行路径压缩
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩，将当前节点直接指向根节点
}
return parent[x]; // 返回根节点
}
// 合并两个集合
public void union(int x, int y) {
int rootX = find(x); // 找到x的根节点
int rootY = find(y); // 找到y的根节点
// 如果根节点相同，说明它们已经在同一个集合中，无需合并
if (rootX == rootY) return;
// 根据秩进行合并，将秩较小的集合合并到秩较大的集合上
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
// 如果秩相等，则随意合并，并将根节点的秩加1
parent[rootY] = rootX;
rank[rootX]++;
}
}
// 判断两个节点是否属于同一个集合
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}
public class Main {
public static void main(String[] args) {
int n = 5; // 节点个数
DisjointSet dsu = new DisjointSet(n);
// 进行一系列合并操作
dsu.union(0, 1);
dsu.union(1, 2);
dsu.union(3, 4);
// 判断节点0和节点2是否属于同一个集合
if (dsu.isConnected(0, 2)) {
System.out.println("节点0和节点2属于同一个集合");
} else {
System.out.println("节点0和节点2不属于同一个集合");
}
}
}
注释解释：
DisjointSet类是并查集的实现类，其中parent数组用于存储每个节点的父节点，rank数组用于存储每个节点的秩（即树的高度或者节点的深度）。find(int x)方法用于查找节点的根节点，同时进行路径压缩，以优化查找速度。union(int x, int y)方法用于合并两个集合，首先找到两个节点的根节点，然后根据秩的大小决定将一个根节点连接到另一个根节点上。isConnected(int x, int y)方法用于判断两个节点是否属于同一个集合，只需要比较它们的根节点是否相同。main方法中演示了如何使用并查集进行集合合并和查询操作。
