[SW][union-find] 3289. 서로소 집합

3289. 서로소집합

 

• 내 풀이
  • 입력범위 주의할것!
  • 1~N까지 받는경우 배열크기 N+1 로 설정해주기

package day16_disjoint_set;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SW3289_ParkSomin {
    static int N,M;
    static String result;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

        int T= Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T ; tc++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            M=Integer.parseInt(st.nextToken());

            result="";
            parent=new int[N+1];
            for (int i = 0; i <= N; i++) {
                parent[i]=i;
            }

            for (int i = 0; i < M; i++) {
                st= new StringTokenizer(br.readLine());
                int c=Integer.parseInt(st.nextToken());
                int a= Integer.parseInt(st.nextToken());
                int b= Integer.parseInt(st.nextToken());

                if(c==0){
                    union(a,b);
                }
                else if(c==1){
                    if (find(a)==find(b)) result+='1';
                    else result+='0';
                }
            }

            System.out.printf("#%d %s", tc,result);
            System.out.println();
        }

    }

    private static void union(int x, int y){
        int a= find(x);
        int b= find(y);
        if (a!=b) parent[b]=a;
    }

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