题目描述

模板

样例

import java.util.*;

public class Main {

    static final int N = 100010;
    //存放点的父结点
    static int[] p = new int[N];
    //表示每一个集合的大小
    static int[] s = new int[N];

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

    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;
            //集合大小初始化
            s[i] = 1;
        }

        while (m-- > 0) {
            String op = scanner.next();
            if (op.equals("C")) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                //如果a和b的祖宗结点相同，说明已经在一个集合里面了， 跳过
                if(find(a) == find(b)) continue;
                //集合b的大小扩大，加上集合a的大小   集合大小是依据根结点的
                s[find(b)] += s[find(a)];
                //a的祖宗结点的父节点为b的祖宗结点
                p[find(a)] = find(b);
            } else if (op.equals("Q1")) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                //如果a和b的祖宗结点相同，说明在一个集合里面
                if (find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            } else {
                int a = scanner.nextInt();
                System.out.println(s[find(a)]);
            }
        }
    }
}