[백준 1717번] 집합의 표현

문제

초기에 {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 를 출력해도 된다)

---

정답

이 문제는 분리 집합을 사용하면 되는 문제이다. 분리집합은 배열 또는 트리 구조로 구현해줄수 있는데 지금 문제의 성격상 배열로 만드는게 옳다. 한개의 집합에는 부모가 하나가 있는데 부모를 찾을 때마다 원소들의 부모값을 새로운 부모로 업데이트 해줘야한다. 안 해주면 실행시간이 커져 시간초과 에러가 뜨게 된다.

부모를 찾을때는 재귀함수를 이용해서 풀어주는것이 더 빠르다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int[] N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String [] NM = br.readLine().split(" ");
        N = new int[Integer.parseInt(NM[0])+1];

        for(int i=0;i<N.length;i++) {
            N[i] = i;
        }

        for(int i=0;i<Integer.parseInt(NM[1]);i++) {
            String [] commands = br.readLine().split(" ");
            int command = Integer.parseInt(commands[0]);
            int a = Integer.parseInt(commands[1]);
            int b = Integer.parseInt(commands[2]);
            if(command == 0) {
                union(a,b);
            }else if(command == 1) {
                check(a,b);
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }
    public static int findParent(int x) {
        if(x == N[x])
            return N[x];
        else
            return N[x]=findParent(N[x]);//부모를 찾을 때마다 최상위 부모로 항상 업데이트 해줘야함
    }
    public static void union(int a, int b) {
        int ap = findParent(a);
        int bp = findParent(b);
        N[bp] = ap;
    }
    public static void check(int a, int b) {
        int ap = findParent(a);
        int bp = findParent(b);
        if(ap!=bp)
            System.out.println("NO");
        else
            System.out.println("YES");
    }

}