【算法】Acwing836 合并集合 （并查集模板题）

原题链接

题目大意

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes

思路：利用并查集对集合进行操作

核心代码

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

accode

import java.util.*;

public class Main{
    static int[] p;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        p = new int[n + 1];
        for(int i = 1; i <= n ; i ++)p[i] = i;//初始化祖宗集合;

        while(m -- > 0){
            String op = sc.next();
            String a = sc.next();
            String b = sc.next();

            if(op.equals("M"))p[find(Integer.parseInt(a))] = find(Integer.parseInt(b));
            else{
                if(find(Integer.parseInt(a)) == find(Integer.parseInt(b)))System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }

    public static int find(int x){//返回祖宗节点+路径压缩
        if(p[x] != x)p[x] = find(p[x]);// x不是自身的父亲，即x不是该集合的代表 查找x的祖先直到找到代表,于是顺手路径压缩
        return p[x];
    }
}