题目描述

初始化n个值每个值都属于自己的集合，然后每次给定两个值，进行和合并和查询两个值是不是同一个区间，是的话输出yes，否则输出n.

输入样例

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例

Yes
No
Yes

算法1

(并查集) $O(n)$

思路：
    1. 暴力的话，合并可以将集合a中元素全部加到b中，当a中元素多的时候很费时间，是否同一个集合的话belong(a)
     == belong(b),判断还算简单
    2. 非暴力 即并查集的做法O(1)
        - 并查集专门就是搞区间的合并和判断是不是属于一个区间
        - 大概可以把集合想象成多颗树，合并的话只需要将某个树的树根放到要合并的树的根的下面 p[x] = y
        - 判断是否是同一个集合，直接一直递归找当前节点的父节点直到找到根，find(x)
        - 如何优化查找？路径压缩
            - 让每次查找的每个节点都指向根节点，所有只要递归几次就可以了

时间复杂度： $O(n)$

参考文献：y总

Java代码

import java.io.*;

public class Main {
    static int N = 100010;
    static int[] p = new int[N];// 存储每个节点的父节点
    // 核心代码
    // 找到当前节点的根节点 + 路径压缩
    static int find(int x){
        if (p[x] != x){// 如果父节点不等于根节点
            int t = find(p[x]);// 查找当前节点的父节点的父节点 直到找到根节点
            return t;
        }
        return x;// 返回根节点
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);

        // 初始化集合 每个节点的父节点是自己
        // 注意 根节点的父节点也是自己
        for (int i = 1; i <= n; i++) p[i] = i;
        while (m-- > 0){
            s1 = br.readLine().split(" ");
            int x = Integer.parseInt(s1[1]);
            int y = Integer.parseInt(s1[2]);
            if ("M".equals(s1[0])) {// 集合合并
                // 找到x,y的根节点 让x的根节点的父节点 = y的根节点
                p[find(x)] = find(y);
            }else {// 查询是否是同一个集合
                if (find(x) == find(y)){
                    // 根节点相同
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }

        br.close();
    }
}

优雅的代码

import java.io.*;

public class Main{
    static int[] p = new int[100010];

    static int find(int x){
        if (p[x] != x) return find(p[x]);
        return x;
    }

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

        for (int i = 1; i <= n; i++) p[i] = i;

        while (m-- > 0){
            s = br.readLine().split(" ");
            int x = Integer.parseInt(s[1]);
            int y = Integer.parseInt(s[2]);
            if ("M".equals(s[0])) p[find(x)] = find(y);
            else {
                if (find(x) == find(y)) System.out.println("Yes");
                else System.out.println("No");
            }
        }

        br.close();
    }
}