并查集
基本思想:
每个集合用一颗树来表示,树根的编号就是整个集合的编号。
每个节点存储它的父节点,p[x]表示x的父节点。
三个问题
P1:如何判断树根
if(p[x]==x)即根节点和输入的集合编号(它本身)相等
P2:如何求x的集合编号
if(p[x]==x) return p[x];
P3:如何合并两个集合
p[x]是x的集合编号,p[y]是y的集合编号
那么,需要让p[x]接上y,即x的祖宗节点为y的一个子节点。
返回祖宗节点:
return p[x];
如果p[x]等于x的话,就返回p[x]即根节点x,此时的返回值为常量x。
路径压缩:
if(p[x]!=x)p[x]=find(p[x]);
代码解读:
如果p[x]不等于x的话,就进行路径压缩操作,即让每个p[x]与自身进行比较,很明显相等,返回的均是x,这样就实现了路径压缩。
分析过程图
代码
import java.util.*;
public class Main{
static int N=100010;
static int p[]=new int[N];
public static int find(int x){//返回祖宗节点+路径压缩
//条件:节点的父节点p[x]为x(祖宗节点)
//换句话来说,即只有祖宗节点等于它本身x
if(p[x]!=x)p[x]=find(p[x]);//路径压缩
return p[x];//返回祖宗节点
}
//等同于如下代码:
public static int find (int x){
if(p[x]==x)return x;
else{
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=1;i<=n;i++)p[i]=i;
while(m-->0){
String s=in.next();
int a=in.nextInt();
int b=in.nextInt();
//合并,将a的祖宗节点作为b的一个子节点插入
if(s.equals("M"))p[find(a)]=find(b);
else{//查找b和a的集合编号是否一致
if(find(b)==find(a)){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}
}
}
这两个视频都挺好的,find函数还有别的版本易于理解的,y总的比较精简!
参考资源:
【图论——并查集(详细版)-哔哩哔哩】 https://b23.tv/UDjPN9Y
【110 并查集-哔哩哔哩】 https://b23.tv/13OXh8I