[백준] 집합의 표현 (1717)

• Union-Find의 기본 문제이다.

import java.util.Scanner;

public class Main {
    static int n,m;
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n+1];
        for(int i=1;i<=n;i++) {
            arr[i] = i;
        }
        for(int i=0;i<m;i++) {
            int sel = sc.nextInt();
            int f = sc.nextInt();
            int l = sc.nextInt();
            if(sel==0) {
                union(f,l);
            }else {
                if(find(f)==find(l)) {
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }
            }
        }
    }
    static void union(int a,int b) {
        int num1 = find(a); // 부모를 찾는다.
        int num2 = find(b);
        if(num1>num2) { // 부모를 정해준다.
            int temp = num2;
            num2 = num1;
            num1 = temp;
        }
        arr[num2] = num1;
    }
    static int find(int a) {
        if(arr[a] == a) {
            return a;
        }
        return arr[a] = find(arr[a]); // 배열에 다시 재입력하므로 시간을 절약할 수 있다
    }
}