题目描述

模板

样例

import java.util.*;

public class Main {

    static final int N = 100010;
    //存放点的父结点
    static int[] p = new int[N];

    //返回x的祖宗结点 + 路径压缩
    static int find(int x) {
        //如果x不是根节点，我们就让x的父节点=祖宗结点
        if (p[x] != x) p[x] = find(p[x]);
        //返回x的父节点
        return p[x];
    }

    //合并集合
    static void merge(int a, int b) {
        //find(a)返回的是a的祖宗结点，find(b)返回的是b的祖宗结点
        //p[find(a)] = find(b)其实就是a的祖宗结点的父节点为b的祖宗结点
        p[find(a)] = find(b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            //初始化
            p[i] = i;
            r[i] = 1;
        }

        while (m-- > 0) {
            char[] op = scanner.next().toCharArray();
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if (op[0] == 'Q') {
                //如果a和b的祖宗结点相同，说明在一个集合里面
                if (find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            } else merge(a, b);
        }
    }
}