前导
几乎和并查集的代码是一模一样的, 因为增加了一项输出连通块数量的操作,所以要再原来的代码上加上一些东西
这就要求我们在面试或者比赛的时候随机应变,但是核心知识点是不会变的,也就是模板也不会变太多,只要把核心理解了,就能让我们举一反三
增加内容
我们使用一个size[]数组来存储树的大小,有三个需要注意的问题
- size[]初始化
- if(find(a) == find(b)) continue;含义
- size[find(b)] += size[find(a)] 和 p[find(a)] = find(b)的先后位置
解答
1:因为一开始是一个个单独的节点,并没有形成树化结构,所以我们初始化为1就可以了
2:如果a,b已经连在一起了,就不用在加了,再相加的话就相当于多加了一遍,所以跳出循环就可以了
3:注意:一定要size[find(b)] += size[find(a)]在前,p[find(a)] = find(b)在后
如果p[find(a)] = find(b)在前的话,再次寻找根节点会找到b,这样的话就是size[find(b)] + size[find(b)]
而不是size[find(b)] + size[find(a)]
代码
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] p = new int[N]; //储存当前节点的父节点
static int[] size = new int[N]; //储存树的大小
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 ++){
p[i] = i;
size[i] = 1;
}
while(m-- > 0)
{
String str = in.next();
int a = in.nextInt();
if(str.equals("C"))
{
int b = in.nextInt();
if(find(a) == find(b)) continue; //如果a,b已经连在一起了,就不用在加了
size[find(b)] += size[find(a)]; //把根节点的大小加在一起
p[find(a)] = find(b); //注意:这条语句要在最后,如果在前面的话,再寻找根节点都会找到b
}
else if(str.equals("Q1"))
{
int b = in.nextInt();
if(find(a) == find(b)) System.out.println("Yes");
else System.out.println("No");
}
else if(str.equals("Q2"))
{
System.out.println(size[find(a)]);
}
}
}
private static int find(int x){ //用于寻找根节点
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
}