AcWing 836. 合并集合
原题链接
简单
作者:
没有你哪有我
,
2022-02-16 15:27:07
,
所有人可见
,
阅读 165
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = 100000 + 10;
// 存储祖先元素
static int[] p = new int[N];
static int n;
static int m;
// find函数 并查集+路径压缩
// find(x) 查找x的祖先
public static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
// 这里要特别注意,不要因为最后一次递归 p[x] == x,就认为返回x 和 p[x]是一样的,其实不是,一开始就犯了这个错误
// 因为我们要返回的是当前x的祖先,不是x本身
return p[x];
}
public static void main(String[] args) throws Exception{
String[] s = r.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
// init
for (int i = 1; i <= n; i ++ ) p[i] = i;
// m次操作
while (m -- > 0) {
s = r.readLine().split(" ");
int a = Integer.parseInt(s[1]);
int b = Integer.parseInt(s[2]);
if (s[0].equals("M")) {
// 将a集合合并到b集合,即将b的祖先作为a的祖先
p[find(a)] = find(b);
} else {
if (find(a) == find(b)) {
w.write("Yes\n");
} else {
w.write("No\n");
}
}
}
w.flush();
}
}
沙雕
菜
[HTML_REMOVED]