AcWing 836. 合并集合原题链接简单

作者：

MyACValentine , 2023-01-25 21:48:24 , 所有人可见 , 阅读 29

并查集

基本思想：
每个集合用一颗树来表示，树根的编号就是整个集合的编号。
每个节点存储它的父节点，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，这样就实现了路径压缩。

分析过程图

过程图.jpg

代码

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");
                }
            }
        }
    }
}