19873连通块中点的数量
19873连通块中点的数量
⭐️难度:中等
🌟考点:连通块、并查集
📖
📚
package test;
import java.util.Scanner;
public class Main {
static int N = 100010;
static int[] a = new int[N];
static int[] p = new int[N];
static int[] size = new int[N];
static int n;
static int m;
// 路径优化
static int find(int x) {
return p[x] == x ? x : (p[x] = find(p[x]));
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 初始化并查集
for (int i = 1; i <= n; i++) {
a[i] = i;
p[i] = i; // 每个点的父节点初始化为自身
size[i] = 1;
}
for (int i = 1; i <= m; i++) {
String op = sc.next();
if (op.equals("C")) {
int x = sc.nextInt();
int y = sc.nextInt();
int px = find(x);
int py = find(y);
if (px != py) {
size[py] += size[px]; // 先更新 size 数组
p[px] = py; // 再合并
}
} else if (op.equals("Q1")) {
int x = sc.nextInt();
int y = sc.nextInt();
if (find(x) == find(y)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
} else {
int x = sc.nextInt();
System.out.println(size[find(x)]);
}
}
}
}