[Do It! 코딩테스트 자바편(김종관)] 문제 050(백준 1717번)

특징

• 순수하게 유니온-파인드 알고리즘 구현만 요구하는 문제라서 알고리즘 복습용 문제로 최적인 것 같다.

문제

집합의 표현 (백준: 1717번)

풀이

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

public class Main {
    static int n, m;
    static int[] set;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        set = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            set[i] = i;
        }

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

            if (flag == 0) {
                union(a, b);
            } else {
                if (find(a) == find(b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }

    }

    private static void union(int a, int b) {
        int rootOfA = find(a);
        int rootOfB = find(b);
        if (rootOfA == rootOfB) {
            return;
        } else {
            if (rootOfA <= rootOfB) {
                set[rootOfB] = rootOfA;
            } else {
                set[rootOfA] = rootOfB;
            }
        }
    }

    private static int find(int index) {
        if (index == set[index]) {
            return index;
        } else {
            return set[index] = find(set[index]);
        }
    }

}