1.思路
刚开始的时候每个点都是在独立的集合中,那我们如何表示两个集合合并呢?这里我们用并查集来解决。我们可以假设每个集合都是一颗多叉树,并且只有一个根结点(每个节点指向自己的父亲节点),这样我们就可以很容易合并两个集合(用一个集合的的根节点连接到另外一个集合的根节点)。这样之后我们就可以很快的判断两个数是否在同一个集合(递归寻找他们的父节点,如果根节点相同,则代表这两个数在一个集合中)。我们这里有一个优化:当我们一个数想要寻找他的根节点时,可以把结果的所有父节点都直接指向根节点。这个优化就叫做路径压缩。我们这题是用的数字来模拟的多叉树,因为每个节点就只有指向父亲节点的指针,并且每个节点默认父亲节点为自己。
2.代码模板
import java.util.*;
public class Main {
static int[] p = new int[100010]; //数组模拟树,表示每个节点的父亲节点是谁
public static int find(int x) { //查找根节点,并且把路径上所有的父节点也指向根节点
if(p[x] != x)
p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
for(int i = 0; i <= n; i++) //默认所有节点的父节点是自己
p[i] = i;
while(m --> 0) {
String op = in.next();
int a = in.nextInt();
int b = in.nextInt();
if(op.equals("M")) //合并两个集合
p[find(a)] = find(b); //使a的根节点指向b的根节点
else {
if(find(b) == find(a)) //如果两个数根节点相同
System.out.println("Yes");
else
System.out.println("No");
}
}
}
}
3.复杂度分析
- 时间复杂度:O(logn)
- 空间复杂度:O(n)