洛谷P 3367【テンプレート】そして調査集

洛谷P 3367【テンプレート】そして調査集
タイトルの説明
問題のように、集計とクエリーの操作を完了する必要があります.
入力フォーマット
第1行は2つの整数N N N,M M Mを含み,N N N個の要素とM M個の動作が共有されていることを示す.
次にM M M行、各行は3つの整数Z i Z_を含む{i} Zi​, X i Xi Xi, Y i Yi Yi.
Z i Z_{i}Zi=1の場合、X i Xi XiとY i Yi Yiが存在する集合をマージします.
Z i Z_{i}Zi=2の場合、出力X i Xi XiとY i Yi Yiが同一集合内にあるか否かは、Y Yの出力である.そうでなければN N Nを出力する.
出力フォーマット
各Z i Z_について{i}Zi=2の操作には、1行の出力があり、各行にはY YまたはYの大文字が含まれています.N N N
入出力サンプル
入力#1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

出力#1

N
Y
N
Y

説明/ヒント
30%30%30%30%%のデータに対して、N N N≤le≤10 10 10、M≤20 Mle 20 M≤20である.
70%70%70%70%%のデータに対して、N≦100 Nle 100 N≦100、M≦1 0 3 Mle 10^3 M≦103である.
100 100%100%100%100%100%%のデータに対して、1≦N≦1 0 4 1le Nle 10^4 1≦N≦104、1≦M≦2× 1 0 5 1\le M\le 2\times10^5 1≤M≤2×105 .
コード実装

import java.util.Scanner;

public class P3367 {
     

    public static int n;        //    

    public static void main(String[] args) {
     

        Scanner sc=new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();

        int[] parent = new int[n+1];
        int[] rank = new int[n+1];
        init(parent,rank);

        for(int i=0;i<m;i++){
     

            int z = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            if(z == 1){
     
                //    
                union_root(x,y,parent,rank);
            }else if(z == 2){
     
                //             
                int result = equ_root(x,y,parent);
                if(result == 0){
     
                    System.out.println("Y");
                }else{
     
                    System.out.println("N");
                }
            }
        }
    }

    public static void init(int parent[], int rank[]){
     
        for(int i=1;i<=n;i++){
          //     
            parent[i] = -1;
            rank[i] = 0;
        }
    }

    public static int find_root(int x ,int parent[]){
     
        int x_root = x;                 //     
        while(parent[x_root] != -1){
     
            x_root = parent[x_root];
        }
        return x_root;
    }

    /* 
                     
       0-       ， 1-        
    */
    public static int equ_root(int x, int y, int parent[]){
     
        int x_root = find_root(x,parent);      
        int y_root = find_root(y,parent);
        if(x_root == y_root){
     
            return 0;
        }else{
     
            return 1;
        }
    }
    
    /*      */
    public static void union_root(int x, int y, int parent[], int rank[]){
     
        int x_root = find_root(x,parent);
        int y_root = find_root(y,parent);

        if(x_root != y_root){
     
            if(rank[x_root] > rank[y_root]){
     
                parent[y_root] = x_root;
            }else if(rank[x_root] < rank[y_root]){
     
                parent[x_root] = y_root;
            }else{
     
                parent[x_root] = y_root;
                rank[y_root]++;
            }
        }
    }
}