题目描述

连通块

JAVA 代码

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

class Main{
    static int N = 100010;
    //size数组值有祖先节点的size才可被用
    static int[] p = new int[N], size = new int[N];

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

        for(int i = 1; i <=n; i++){
            p[i] = i;
            // 维护一个size 数组, 初始值都 = 1
            size[i] = 1;
        }

        while(m-->0){
            s = in.readLine().split(" ");
            String c = s[0];

            if(c.equals("C")){
                int a = find(Integer.parseInt(s[1]));
                int b = find(Integer.parseInt(s[2]));
                if(a != b){
                    p[a] = b;
                    //每次合并, 祖先节点的值+= 合并过来的节点.
                    size[b] += size[a];
                }
            }else if(c.equals("Q1")){
                int a = find(Integer.parseInt(s[1]));
                int b = find(Integer.parseInt(s[2]));
                if(a == b)System.out.println("Yes");
                else System.out.println("No");
            }else{
                int a = Integer.parseInt(s[1]);
                System.out.println(size[find(a)]);
            }


        }

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

}