并查集的难点在合并,哪个是属于哪个家族的,如果两个都有家族合并累死了
int find(int x)//返回x的祖宗结点+路径压缩
{
if(p[x]!=x)p[x]=find(p[x]);//让每个父结点等于祖宗结点
return p[x];//返回父结点(即祖宗结点)
}
合并a,b: p[find(a)]=find(b)
让a的祖宗结点的父结点等于b的祖宗结点
题目描述
现在要进行 m 个操作,操作共有两种:
M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
Q a b,询问编号为 a 和 b 的两个数是否在同一个集合中;
算法1
(并查集) $O(1)$
p[x]存父结点,根结点的父结点就是自己
while (p[x]!==x)x=p[x]//只要不是树根就一直往上走
要合并:找到被合并的根结点,给它一个父结点
优化:路径压缩
java 代码
import java.util.*;
public class Main{
static int n,m;
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 scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
for(int i=1;i<=n;i++){
p[i]=i;
}
while(m-->0){
String op=scan.next();
int a=scan.nextInt();
int b=scan.nextInt();
if(op.equals("M"))p[find(a)]=find(b);
if(op.equals("Q")){
if(find(a)==find(b))System.out.println("Yes");
else System.out.println("No");
}
}
}
}