[백준 1717] 집합의 표현 / 자바 / 자료구조(유니온 파이든)

#문제         

레벨: G5
알고리즘: 자료구조(유니온 파이든) 
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

이 문제는 "Disjoint Set(분리 집합)" 또는 "Union-Find" 알고리즘을 사용하여 효율적으로 해결할 수 있다.

유니온 파인드 자료구조는 자기의 부모를 기록하는 것이다. 

위 그림에서 2와 3이 같은 집합인지 알려면 최상위 부모가 같은지 확인 하는 거다. 

집합을 추가하는 방법은 또 그림으로 설명하겠다. 3과 6이 같은 집합인 걸 알고 집합을 추가할 때, 6의 최상위 부모인 7과 3의 최상위 부모인 1를 자식-부모 관계로 만들면 된다. 1을 자식으로 두던 7을 자식으로 두던 그건 구현하는 사람 마음이다.

---

#풀이 코드      

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

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        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 operation = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (operation == 0) {
                union(a, b);
            } else if (operation == 1) {
                if (find(a) == find(b)) {
                    bw.write("YES\n");
                } else {
                    bw.write("NO\n");
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }
}