AcWing 837. 连通块中点的数量JAVA
原题链接
简单
作者:
w972314191
,
2022-12-02 11:34:20
,
所有人可见
,
阅读 122
代码
import java.util.*;
import java.io.*;
public class Main{
static int N = 100010;
static int[] father = new int[N];
static int[] cnt = new int[N];
static int findFather(int x){
if(father[x] != x) father[x] = findFather(father[x]);
return father[x];
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Integer[] line0 = Arrays.stream(br.readLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
int n = line0[0];
int m = line0[1];
for(int i = 0; i < n; i++){
father[i] = i;
cnt[i] = 1;
}
while(m-->0){
String[] line = br.readLine().split(" ");
String op = line[0];
int a = Integer.parseInt(line[1]) - 1;
if(op.compareTo("C") == 0){
int b = Integer.parseInt(line[2]) - 1;
//果然是易错点,Y总讲的时候忘了,自己写的时候也容易忘
if(findFather(a) != findFather(b)){
cnt[findFather(b)] += cnt[findFather(a)];
father[findFather(a)] = findFather(b);
}
}else if(op.compareTo("Q1") == 0){
int b = Integer.parseInt(line[2]) - 1;
if(findFather(a) == findFather(b)){
bw.write("Yes\n");
}else{
bw.write("No\n");
}
}else{
bw.write(cnt[findFather(a)] + "\n");
}
}
bw.flush();
br.close();
bw.close();
}
}