题目描述
原题链接:https://www.acwing.com/problem/content/838/
样例
import java.util.Scanner;
public class Main {
static int N = 100010;
static int n;// 1-n个数
static int m;// m个操作
static int p[] = new int[N];// 集合元素
static String op;// 操作
static int a;// 读元素
static int b;// 读元素
static StringBuilder stb = new StringBuilder();
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
// 1-n个数,每个元素在单独的一个集合中,即根元素是自己
for(int i = 1 ; i <= n; i++) {
p[i] = i;
}
// 读入操作
for(int i = 0; i < m; i++) {
op = scan.next();
a = scan.nextInt();
b = scan.nextInt();
// 合并两个集合
// 查到a的父节点和b的父节点,将a的父节点设置为b的父节点,就将a接入到b下面了
if(op.equals("M")) {
p[find(a)] = find(b);
} else {
// 输入不是"M"则代表是"Q":查询两个元素是否在同一个集合
// 分别查询他们的父节点,父节点相同说明是同一个集合
if(find(a) == find(b)) {
stb.append("Yes" + "\n");
} else {
stb.append("No" + "\n");
}
}
}
System.out.print(stb.toString());
scan.close();
}
// 传入元素x,查询x的根节点
public static int find(int x) {
// 如果节点不等于自身 说明不是根节点,从父节点开始继续往上查
// 通过递归得到根节点,对p[x]赋值,完成路径压缩,
// 路径压缩能让该根节点下的所有元素的父节点都指向根节点,极大压缩了后续的查询次数
if(p[x] != x) {
p[x] = find(p[x]);
}
// 最终得到根节点返回
return p[x];
}
}