[Java] SWEA - 서로소 집합

집합을 합치고 집합에 포함되는지 확인한 결과를 출력하는 문제입니다.

입력 받은 연산을 통해서 두 집합을 하나의 집합으로 만들어주었습니다.

집합을 처리하기 위해서 n크기의 배열을 만들어서 각자 자신을 부모로 가르키게 하였습니다.
집합이 합쳐질 경우 하나의 집합의 부모를 합쳐지는 집합을 가르키게 하였습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Solution {
  public static void main(String[] args) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      StringTokenizer st;
      int testcase = Integer.parseInt(br.readLine());
       
      for(int t=1; t<=testcase; ++t) {
        bw.write("#" + t + " ");
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n+1];
         
        for(int i=1; i<=n; ++i) {
            arr[i] = i;
        }
         
        for(int i=0; i<m; ++i) {
            st = new StringTokenizer(br.readLine());
            int cal = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
             
            if(cal == 0) {
                int rootA = a;
                int rootB = b;
                while(rootA != arr[rootA]) {
                    rootA = arr[rootA];
                }
                while(rootB != arr[rootB]) {
                    rootB = arr[rootB];
                }
                if(rootA < rootB) {
                    arr[rootA] = rootB;
                } else if (rootA > rootB) {
                    arr[rootB] = rootA;
                     
                }
            } else if (cal == 1) {
                int rootA = a;
                int rootB = b;
                while(rootA != arr[rootA]) {
                    rootA = arr[rootA];
                }
                while(rootB != arr[rootB]) {
                    rootB = arr[rootB];
                }
                if(rootA == rootB) {
                    bw.write("1");
                } else {
                    bw.write("0");
                }
            }
        }
        bw.write("\n");
      }
      bw.close();
  }
}