66 并查集的实现
Table of Contents

ac

import java.util.*;
import java.io.*;
public class Main {
    static public int[] p;//根节点
    static public int[] rank;//秩

    public static void init(int n){
        //初始化
        p = new int[n+1];
        for(int i=0;i<p.length;i++){
            p[i] = i;
        }
        rank = new int[n+1];
        for(int i=0;i<rank.length;i++){
            rank[i] = 0;
        }
    }

    public static int find(int x){
        return x==p[x] ? x:(p[x] = find(p[x]));
    }

    public static void union(int x1, int x2){
        // 查找根节点
        int f1 = find(x1);
        int f2 = find(x2);
        if(f1 == f2){
            return;
        }
        /**
         * 按秩合并两个集合,rank大的作为父节点,以减少树的层数
         * 秩较小的作为子树,放到秩较大的节点下面
         */
        if(rank[f1] > rank[f2]){
            p[f2] = f1;
        }else{
            p[f1] = f2;
            if(rank[f1] == rank[f2]){//新树秩+1
                ++rank[f2];
            }
        }
    }

    public static boolean isSameSet(int a, int b){
        return find(a)== find(b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String line = bf.readLine();
        String[] strings = line.split(" ");
        int N = Integer.parseInt(strings[0]);
        int M = Integer.parseInt(strings[1]);
        init(N);
        ArrayList res = new ArrayList();
        for(int i=0;i<M;i++){
            String[] ss = bf.readLine().split(" ");
            int opt = Integer.parseInt(ss[0]);
            int a = Integer.parseInt(ss[1]);
            int b = Integer.parseInt(ss[2]);
            if(opt == 1){
                res.add(isSameSet(a,b)==true?"Yes":"No");
            }else{
                union(a,b);
            }
        }

        //输出结果
        StringBuilder sb = new StringBuilder();
        if(res.size() >= 1){
            sb.append(res.get(0));
        }
        for(int i=1;i<res.size();i++){
           sb.append("\n" + res.get(i));
        }
        System.out.println(sb.toString());
    }

}
/*
4 5
1 1 2
2 2 3
2 1 3
1 1 1
1 2 3

No
Yes
Yes
 */