题解 | #并查集的实现#

import java.io.*;

/**
 * ClassName: Code
 * pACKAGE: UnionLookUpSet
 * Description:
 * 并查集相关代码的实现
 * 平均时间复杂度:o(1)
 * @Author hz
 * @Create: 2023/10/4 - 16:47
 * @Version :v1.0
 */
public class Main {
   
    public static int MAX=1000001;
    public static int[]father=new int[MAX];
    public static int[]size=new int[MAX];//只有代表节点的size信息是有用的
    public static int[]stack=new int[MAX];
    public static int n; //每个节点用它的编号表示也是father和size数组中的下标
    public static void build(){//并查集初始化
        for(int i=0;i<=n;i++){
            father[i]=i;
            size[i]=1;
        }
    }
    //i号节点，一直往上找，找到代表节点，返回  其中带有扁平化:是在find()的过程中实现的
    public static int find(int i){//优化二:扁平化的优化
        int size=0;//沿途收集了几个点
        while (i!=father[i]){
            stack[size++]=i;
            i=father[i];
        }
        //沿途节点收集好了,i已经跳到代表节点
        while (size>0){
            father[stack[--size]]=i; //扁平化过程
        }
        return i;
    }
    public static boolean isSameSet(int x,int y){
        return find(x)==find(y);
    }
    public static void union(int x,int y) {
        int fx = find(x);//x节点所在集合的代表节点
        int fy = find(y);//y节点所在集合的代表节点
        //优化一:小挂大的优化
        if (fx != fy) {  //不是一个集合的情况下
            //fx代表:大小
            //fy代表:大小
            if (size[fx] > size[fy]) {
                size[fx] += size[fy];
                father[fy] = fx;
            } else {
                size[fy] += size[fx];
                father[fx] = fy;
            }
        }
    }
    // 以上为并查集相关代码的是实现:两个优化:扁平化和小挂大的优化
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] s = br.readLine().split(" ");
         n=Integer.parseInt(s[0]);//表示数组大小
         int m=Integer.parseInt(s[1]);//表示操作次数
         build();
         for(int i=0;i<m;i++){
             String[] s1 = br.readLine().split(" ");
             int op=Integer.parseInt(s1[0]);
             int x=Integer.parseInt(s1[1]);
             int y=Integer.parseInt(s1[2]);
             if(op==1){
                 if(isSameSet(x,y)) out.println("Yes");
                 else out.println("No");
                 out.flush();
             }else union(x,y);
         }
    }
}