BOJ1717 집합의 표현 java - 분리 집합 [1]

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

a를 포함하는 집합과 b를 포함하는 집합을 합치거나 같은 집합에 포함되어 있는지 확인하는 문제이다.

문제에서 직관적으로 분리 집합 문제임을 보여주고 있다.

import java.util.*;
import java.io.*;

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int M = Integer.valueOf(st.nextToken());

        StringBuilder sb = new StringBuilder();

        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 action = Integer.valueOf(st.nextToken());
            int a = Integer.valueOf(st.nextToken());
            int b = Integer.valueOf(st.nextToken());
            if(action == 0) {
                union(a,b);
            } else {
                sb.append(solution(a,b));
            }
        }

        System.out.println(sb.toString());

    }
    private static String solution(int a, int b) {
        String result = "NO\\n";
        if(find(a) == find(b)) {
            result = "YES\\n";
        }
        return result;
    }

    private static int find(int x) {
        // 루트 노드는 부모 노드 번호로 자기 자신을 가지므로 같으면 리턴
        if(parent[x] == x) {
            return x;
        }

        // 각 노드의 부모 노드를 찾아 올라간다.
        return find(parent[x]);
    }

    private static void union(int u, int v) {
        // 각 원소가 속한 트리의 루트 노드를 찾는다.
        u = find(u);
        v = find(v);

        if(u != v) {
            parent[v] = u;
        }
    }
}