并查集(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
方法合并两个集合。本文介绍了并查集算法的实现,并给出了一个示例代码。并查集是一种用于处理集合合并与查询问题的数据结构,它的核心思想是通过维护每个元素的父节点来表示集合之间的关系。通过路径压缩和按秩合并等优化策略,可以提高并查集算法的效率。
希望本文对你理解并查集算法有所帮助!