1.思路
和并查集思路差不多,只不过多了一点额外信息。我们用sum[]来存储当前节点下的连通节点数量,为了计算该连通块中节点的个数。
2.代码模板
import java.util.*;
public class Main {
static int[] a = new int[100010]; //数组模拟树,表示每个节点的父亲节点是谁
static int[] sum = new int[100010]; //计算每个节点下的连通节点数量
static int find(int x) { //查找根节点,并且把路径上所有的父节点也指向根节点
if(a[x] != x)
a[x] = find(a[x]);
return a[x];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
for(int i = 1; i <= n; i++) {
a[i] = i; //默认所有节点的父节点是自己
sum[i] = 1; //因为自己和自己连通了,所以该节点下连通数量为1
}
while(m --> 0) {
String s = in.next();
int b, c;
if(s.equals("C")) {
b = in.nextInt();
c = in.nextInt();
b = find(b); //找到b的根节点
c = find(c); //找到c的根节点
if(b != c) { //说明不在同一个连通块中
a[b] = c; //将两个块连通在一起,把b连到c下,此时c为根节点,b为c的子节点
sum[c] += sum[b]; //计算c,b连接之后连通块中的数量
}
} else if(s.equals("Q1")) {
b = in.nextInt();
c = in.nextInt();
if(find(b) == find(c)) //如果两个数根节点相同
System.out.println("Yes");
else
System.out.println("No");
} else {
b = in.nextInt();
System.out.println(sum[find(b)]); //找到b的根节点,其数量就是该连通块的节点数量
}
}
}
}