[BOJ] 백준 1717 집합의 표현

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

 Input 

7 8

0 1 3

1 1 7

0 7 6

1 7 1

0 3 7

0 4 2

0 1 1

1 1 1

 

 Output 

NO

NO

YES

▶ 0 a b → union

▶ 1 a b → find

※ Disjoint-Set & Union-Find 

Disjoint-Set & Union-Find

시뮬레이션

 

▶union(1, 3) → find(1, 7)

 

▶ union(7, 6) → find(7, 1)

 

▶ union(3 7), union(4, 2), union(1, 1) → find(1, 1)

* 부모노드를 설정할 때, 낮은 번호 정점이 부모 노드가 되도록 설정

▶ 집합을 {0} / {1, 3, 6, 7} / {2, 4} / {5}로 구분할 수 있습니다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int[] parent;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        parent = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            // 0을 포함해서 초기화
            parent[i] = i;
        }
 
        int M = Integer.parseInt(st.nextToken());
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int opr = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            if (opr == 0) union(a, b);
            else System.out.println(find(a, b) ? "YES" : "NO");
        }
    }
     
    // (root) 부모 노드 찾기
    private static int getParent(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = getParent(parent[x]);
    }
 
    // 집합 합치기
    private static void union(int a, int b) {
        a = getParent(a);
        b = getParent(b);
         
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }
 
    // 같은 집합인지 확인
    private static boolean find(int a, int b) {
        if (getParent(a) == getParent(b))
            return true;
        return false;
    }
}