题解 | #并查集的实现#

public class h9a14 {
    static public int[] p;//根节点
    static public int[] rank;//秩

    public static void init(int n) {
        //初始化p[i]：第i个集合的根节点[第1个——第N个集合]
        p = new int[n + 1];
        for (int i = 0; i < p.length; i++) {
            p[i] = i;
        }
        //ran[i]：第i个集合一共有多少个元素
        rank = new int[n + 1];
        for (int i = 0; i < rank.length; i++) {
            rank[i] = 1;
        }
    }

    //查询节点对应的集合的根节点
    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;
        //按秩合并两个集合
        if (rank[f1] >= rank[f2]) {
            p[f2] = f1;
            rank[f1] += rank[f2];
        } else {
            p[f1] = f2;
            rank[f2] += rank[f1];
        }
    }

    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);    //初始化，创建出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);
            }
        }

        //输出结果
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }

}