9-并查集

算法思想

基本并查集

• 每个集合用一个树来表示
• 根节点存储集合的编号
  • 根节点的编号就是集合的编号
• 每个子节点存储其父节点的编号

使用路径优化的并查集

• 每个子节点存储集合的编号，即根节点的编号

算法模板

import java.util.*;
public class Main {
    static int N = 100010;
    static int[] p = new int[N];
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 1; i <= n; i ++) p[i] = i;
        while(m -- > 0)
        {
            String s = sc.next();
            int x = sc.nextInt();
            int y = sc.nextInt();
            if(s.equals("M"))
            {
                // 合并两个集合
                if(find(x) != find(y)) p[find(y)] = find(x);
            }
            else 
            {
				var res = find(x) == find(y) ? "Yes" : "No";
				System.out.println(res);
            }
        }
    }

	// 路径优化查找法
    static int find(int x)
    {
	    // 递归标准写法
        // if(p[x] == x) return p[x];

	    // p[x] = find(p[x]);
	    // return p[x];

	    // 简化写法
	    // 不结束条件与递归体
	    if(p[x] != x) p[x] = find(p[x]);
	    return p[x];
    }
}