AcWing 837. 连通块中点的数量-java简单版
原题链接
简单
作者:
Astarion
,
2021-02-05 11:16:19
,
所有人可见
,
阅读 691
import java.io.*;
class Main {
static int[] p = new int[100010];
static int[] cnt = new int[100010];
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 {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
String[] strs = in.readLine().split(" ");
int n = Integer.parseInt(strs[0]);
int m = Integer.parseInt(strs[1]);
//初始化p数组
for (int i = 1; i<=n; i++) {
p[i] = i;
cnt[i] = 1;
}
for (int i = 0; i<m ;i++) {
strs = in.readLine().split(" ");
switch (strs[0]) {
case "Q1" : {
int a = Integer.parseInt(strs[1]);
int b = Integer.parseInt(strs[2]);
if (find(a) == find(b)) System.out.println("Yes");
else System.out.println("No");
break;
}
case "Q2" : {
int a = Integer.parseInt(strs[1]);
System.out.println(cnt[find(a)]);
break;
}
case "C" : {
int a = Integer.parseInt(strs[1]);
int b = Integer.parseInt(strs[2]);
if (find(a) != find(b)) {
cnt[find(b)] += cnt[find(a)];
p[find(a)] = find(b);
}
break;
}
}
}
}
}