백준 1717 집합의 표현 Java [분리집합, Union find]

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

서로 같은 집합에 속해 있는지 확인하기 위해 모든 원소 값들을 자기 자신을 부모로 설정한다

입력값의 가장 첫 값이 0이면 a의 부모에 b의 부모를 넣거나

b의 부모에 a의 부모를 넣는다 (둘 중에 한가지만 일관되게 사용)

1이면 a의 부모와 b의 부모가 같은지 확인한다

여기서 설명하는 부모는 가장 최상위에 자기 자신을 부모로 하는 원소이다

 

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

public class Main {
    static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        parents = new int[N + 1];
        for (int n = 1; n <= N; n++) {
            parents[n] = n;
        }
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (k == 0) {
                union(a, b);
            } else {
                sb.append(findParent(a) == findParent(b) ? "YES" : "NO").append("\n");
            }
        }
        System.out.println(sb);
    }

    static int findParent(int x) {
        if (x == parents[x]) return x;
        return parents[x] = findParent(parents[x]);
    }

    static void union(int x, int y) {
        int px = findParent(x);
        int py = findParent(y);
        if (px != py) parents[py] = px;
    }
}