집합의 표현 - 1717번 문제

이 문제는 Union-find의 대표적인 문제이다

입력중에서 0인 경우 union을 해주면 되고, 1인 경우 find를 해주어서

루트가 똑같을 경우 YES, 아닐 경우 NO를 출력 해 주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
     static int parent[];
     static int rank[];
     public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         String line [] = br.readLine().split(" ");
         int n = Integer.valueOf(line[0]);
         int m = Integer.valueOf(line[1]);
     
         parent = new int[n+1];
         rank = new int[n+1];
         for(int i=1; i<=n; i++) {
             parent[i] = i;
             rank[i] = 0;
         }
         for(int i=0; i<m; i++) {
             line = br.readLine().split(" ");
             if(Integer.valueOf(line[0]) == 0) {
                 union(Integer.valueOf(line[1]), Integer.valueOf(line[2]));
             }
             else {
              
                 if(find(Integer.valueOf(line[1])) == find(Integer.valueOf(line[2])))
                     System.out.println("YES");
                 else
                     System.out.println("NO");
             }
         }
     }
     
     public static int find(int x) {
         if(x == parent[x])
             return x;
         else
             return parent[x] = find(parent[x]);
     }
     
     public static void union(int p, int q) {
         p = find(p);
         q = find(q);
         
         if(p == q)
             return;
         
         if(rank[p] < rank[q])
             parent[p] = q;
         else {
             parent[q] = p;
         }
         
         if(rank[p] == rank[q])
             rank[p]++;
     }
}