AcWing 836. 并 查 集 JAVA
原题链接
简单
作者:
理想二旬.
,
2021-05-11 17:23:39
,
所有人可见
,
阅读 257
JAVA 代码
import java.io.*;
class Main{
private static int N = 100010;
private static int[] p = new int[N]; //存储每个节点的父节点
//寻找祖宗节点
//路径压缩: 由于递归 最后所有的子节点都指向祖宗节点
public static int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
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[] str1 = reader.readLine().split(" ");
int n = Integer.parseInt(str1[0]);
int m = Integer.parseInt(str1[1]);
//根据题意初始化
for(int i = 0; i < n; i ++){
p[i] = i;
}
while(m -- > 0){
String[] str = reader.readLine().split(" ");
//合并操作:将一个集合的祖宗节点变为另一个集合祖宗节点的子节点
if(str[0].equals("M")) p[find(Integer.parseInt(str[1]))] = find(Integer.parseInt(str[2]));
else{
//查询操作,根据find函数返回两个集合的祖宗节点并比较
if(find(Integer.parseInt(str[1])) == find(Integer.parseInt(str[2]))) writer.write("Yes" + "\n");
else writer.write("No" + "\n");
}
}
writer.flush();
writer.close();
reader.close();
}
}