AcWing 836. Java 合并集合 【并查集模板】
原题链接
简单
作者:
ACSaber
,
2020-11-30 14:48:27
,
所有人可见
,
阅读 378
import java.util.*;
import java.io.*;
class Main {
static int N = 100009;
static int[] p = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = reader.readLine().split(" ");
int n = Integer.parseInt(s[0]);
// 一定要先初始化,让 n 个数的 father 指针先指向自己,代表每个数刚开始都是自己一个集合
for (int i = 1; i <= n; i++) {
p[i] = i;
}
int m = Integer.parseInt(s[1]);
for (int i = 0; i < m; i++) {
s = reader.readLine().split(" ");
if (s[0].equals("M")) {
int a = Integer.parseInt(s[1]);
int b = Integer.parseInt(s[2]);
meger(a, b);
} else if (s[0].equals("Q")) {
int a = Integer.parseInt(s[1]);
int b = Integer.parseInt(s[2]);
boolean ans = query(a, b);
writer.write(ans ? "Yes" : "No");
writer.write("\n");
}
}
reader.close();
writer.flush();
writer.close();
}
// 含义为,让 a 节点的祖宗节点的 father 指针指向 b 节点的祖宗节点
private static void meger(int a, int b) {
p[find(a)] = p[find(b)];
}
// 返回 x 的祖宗节点
private static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
private static boolean query(int a, int b) {
return find(a) == find(b);
}
}