1.一开始元素拥有自己的集合，在自己的集合里只有这个元素自己
2.find(i):查找i所在集合的代表元素，代表元素来代表i所在的集合
3.boolean isSameSet(a,b):判断a,b在不在一个集合里
4.void union(a,b):a所在集合所有元素和b所在集合所有元素 合并成一个集合
5.各种操作单次调用的均摊时间复杂度O(1)

find一直往上找 一直找到不能再往上的
优化一 union小的去挂大的
优化二 扁平化(路径压缩)
比如说 2-3 3-4 4-5
find(2)的时候 在找父节点的过程中 我们把沿途的都给直接挂到5
那越调用速度越快，挺好

father 和 size的改变
只有代表节点的size信息有用 也就是最上方的节点对吧
father指向父节点

import java.io.*;

public class Main {
    // n 和 m 为题目给定的总数和操作数
    static int n, m;
    // father[i] 存储 i 的父节点
    static int[] father;
    // size[i] 存储以 i 为根的集合的大小
    static int[] size;
    // 用于路径压缩的栈（临时存储路径上的节点）
    static int[] stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);

        // 初始化并查集
        father = new int[n + 1];
        size = new int[n + 1];
        stack = new int[n + 1];
        build();

        // 处理 m 个操作
        for (int i = 0; i < m; i++) {
            line = br.readLine().split(" ");
            String op = line[0];
            int a = Integer.parseInt(line[1]);
            int b = Integer.parseInt(line[2]);

            if (op.equals("M")) {
                union(a, b);
            } else if (op.equals("Q")) {
                if (isSameSet(a, b)) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
            }
        }
        br.close();
    }

    /**
     * 初始化并查集
     * 每个元素一开始都是一个独立的集合，其父节点是自身，集合大小为1。
     */
    public static void build() {
        for (int i = 1; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    /**
     * 查找根节点并进行路径压缩
     * @param i 待查找的元素
     * @return 元素 i 所在集合的根节点
     */
    public static int find(int i) {
        int tempSize = 0;
        // 向上遍历，直到找到根节点（父节点是自身）
        while (i != father[i]) {
            // 将路径上的节点存入栈中
            stack[tempSize++] = i;
            i = father[i];
        }
        // 路径压缩：将栈中的所有节点直接连接到根节点 i
        while (tempSize > 0) {
            father[stack[--tempSize]] = i;
        }
        return i;
    }

    /**
     * 判断两个元素是否在同一个集合中
     * @param x 元素 x
     * @param y 元素 y
     * @return 如果 x 和 y 的根节点相同，则返回 true
     */
    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    /**
     * 合并两个元素所在的集合（按大小合并）
     * @param x 元素 x
     * @param y 元素 y
     */
    public static void union(int x, int y) {
        int fx = find(x); // 找到 x 的根节点
        int fy = find(y); // 找到 y 的根节点
        if (fx != fy) { // 如果根节点不同，说明不在同一个集合，可以合并
            // 按大小合并：将小集合合并到大集合上
            if (size[fx] >= size[fy]) {
                size[fx] += size[fy]; // 更新大集合的大小
                father[fy] = fx;       // 将小集合的根节点连接到大集合的根节点
            } else {
                size[fy] += size[fx];
                father[fx] = fy;
            }
        }
    }
}