测试链接
介绍
并查集（Disjoint Set）是一种用于处理集合合并与查询问题的数据结构。它支持两种操作：合并（Union）和查询（Find）。
合并操作将两个不相交的集合合并为一个集合，查询操作用于判断两个元素是否属于同一个集合。
本文将介绍并查集算法的实现，并给出一个示例代码。
算法实现
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer sr = new StreamTokenizer(in);
static int MAXN = (int)(1e6 + 10);
static int[] f = new int[MAXN];
static int[] size = new int[MAXN];
static int[] stack = new int[MAXN];
static int n, m;
public static void main(String[] args) throws IOException {
n = nextInt();
m = nextInt();
build();
while (m-- > 0) {
int op = nextInt();
int x = nextInt();
int y = nextInt();
if (op == 1) {
boolean res = isSameSet(x, y);
out.println(isSameSet(x, y) ? "Yes" : "No");
out.flush();
} else if (op == 2) {
union(x, y);
}
}
}
static void build() {
for (int i = 0; i <= n; i++) {
f[i] = i;
size[i] = 1;
}
}
static int find(int i) {
int size = 0;
while (i != f[i]) {
stack[size++] = i;
i = f[i];
}
while (size > 0) {
f[stack[--size]] = i;
}
return i;
}
static boolean isSameSet(int x, int y) {
return find(x) == find(y);
}
static void union(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
if (size[fx] >= size[fy]) {
size[fx] += size[fy];
f[fy] = fx;
} else {
size[fy] += size[fx];
f[fx] = fy;
}
}
}
static int nextInt() throws IOException {
sr.nextToken();
return (int)sr.nval;
}
}
算法解析
- 首先，我们定义了一个并查集的大小
MAXN，并声明了一些用于存储数据的数组和变量。 build方法用于初始化并查集，将每个元素的父节点设置为自身，并将每个集合的大小初始化为 1。find方法用于查找元素所属的集合，通过递归地找到根节点，并将路径上的节点的父节点设置为根节点，以优化后续的查找操作。isSameSet方法用于判断两个元素是否属于同一个集合，通过比较它们的根节点是否相同来判断。union方法用于合并两个集合，首先找到两个元素所属的根节点，然后根据集合的大小来决定合并的方式，将一个集合的根节点指向另一个集合的根节点，并更新集合的大小。- 在
main方法中，我们首先读取输入的元素个数n和操作次数m，然后调用build方法初始化并查集。 - 接下来，根据操作类型进行相应的操作。如果是查询操作，我们调用
isSameSet方法判断两个元素是否属于同一个集合，并输出结果。如果是合并操作，我们调用union方法合并两个集合。 - 最后，我们输出结果并结束程序。
总结
本文介绍了并查集算法的实现，并给出了一个示例代码。并查集是一种用于处理集合合并与查询问题的数据结构，它的核心思想是通过维护每个元素的父节点来表示集合之间的关系。通过路径压缩和按秩合并等优化策略，可以提高并查集算法的效率。
希望本文对你理解并查集算法有所帮助！
