AcWing 837. 连通块中点的数量(Java)
原题链接
简单
作者:
火球大的脸盆
,
2022-07-08 16:02:14
,
所有人可见
,
阅读 132
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static final int N = 100010;
public static int n, m, a, b;
public static int[] p = new int[N], size = new int[N];
public static String op;
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 Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] first_line = br.readLine().split(" ");
n = Integer.parseInt(first_line[0]);
m = Integer.parseInt(first_line[1]);
for (int i = 1; i <= n; i++) {
p[i] = i;
size[i] = 1;
}
while (0 != m--) {
String[] second_line = br.readLine().split(" ");
op = second_line[0];
if ("C".equals(op)) {
a = Integer.parseInt(second_line[1]);
b = Integer.parseInt(second_line[2]);
if (find(a) != find(b))
size[find(a)] += size[find(b)];
p[find(b)] = find(a);
}
else if ("Q1".equals(op)) {
a = Integer.parseInt(second_line[1]);
b = Integer.parseInt(second_line[2]);
if (find(b) == find(a)) {
bw.write("Yes\n");
bw.flush();
}
else {
bw.write("No\n");
bw.flush();
}
}
else if ("Q2".equals(op)) {
a = Integer.parseInt(second_line[1]);
bw.write(size[find(a)] + "\n");
bw.flush();
}
}
}
}