AcWing 836. 合并集合--Java
原题链接
简单
作者:
domiso
,
2021-08-30 13:47:04
,
所有人可见
,
阅读 178
import java.util.*;
public class Main {
static int N = 100010,p[] = new int[N];
static int find(int x) {//返回祖宗节点 + 路径压缩
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] line = sc.nextLine().split(" ");
int n = Integer.parseInt(line[0]), m = Integer.parseInt(line[1]);
for(int i = 1; i <= n; i ++) p[i] = i;
for(int i = 0; i < m;i ++) {
line = sc.nextLine().split(" ");
int a = Integer.parseInt(line[1]), b = Integer.parseInt(line[2]);
if(line[0].equals("M")) {
p[find(a)] = find(b);
}else {
if(find(a) == find(b)) System.out.println("Yes");
else System.out.println("No");
}
}
}
}