题目描述

合并集合 - 【并查集】

时间复杂度

查找第一次 ologn 之后都是o(1)

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    static int N = 100010, n, m;
    static int[] p = new int[N];

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

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

        while(m-->0){
            s = in.readLine().split(" ");
            String c = s[0];
            int a = Integer.parseInt(s[1]);
            int b = Integer.parseInt(s[2]);
            if(c.equals("M")){
                p[find(a)] = find(b);
            }else{
                if(find(a)==find(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]);
        return p[x];
    }


}