[Java] 상호 배타적 집합

상호 배타적 집합

개요

ㄹ

두 원소가 같은 트리에 속했는가?
-> 각 원소가 포함된 트리의 루트를 찾은 뒤 이들이 같은 지 비교

if 루트가 같다면 두 노드가 같은 트리에 속함

else 루트가 다르다면 두 노드가 다른 트리에 속함
-> 합치기 연산 시행

루트 노드는 자기 자신을 가리킴

    static class DisjointSet {
        // parent : 각 노드의 부모 위치
        Vector<Integer> parent;
        // rank : 각 노드의 높이
        Vector<Integer> rank;

        public DisjointSet(int n) {
            parent = new Vector<>();
            rank = new Vector<>();

            // 노드 수 만큼 반복
            for (int i = 0; i < n; i++) {
                // 처음은 자기 자신이 부모
                parent.add(i);
                // 높이는 1로 초기화
                rank.add(1);
            }
        }

        // u가 속한 트리의 루트 번호를 반환한다.
        public int find(int u) {
            // 루트 번호면 자기 자신이므로 끝남.
            if (u == parent.get(u))
                return u;

            // 루트 번호 갱신
            int ret = find(parent.get(u));
            parent.set(u, ret);
            return ret;
        }

        // u가 속한 트리와 v가 속한 트리를 합친다.
        public void merge(int u, int v) {
            // u, v 의 각각 루트 노드 구하기
            u = find(u);
            v = find(v);

            // u, v 가 같은 트리에 속한다면...
            // 바로 종료
            if (u == v)
                return;

            // u의 깊이가 v보다 깊다면..
            // v뒤에 u를 붙이자!
            if (rank.get(u) > rank.get(v)) {
                int tmp = u;
                u = v;
                v = tmp;
            }

            // u의 루트를 v루트 뒤에 붙인다.
            parent.set(u, v);

            if (rank.get(u) == rank.get(v)) {
                rank.set(v, rank.get(v) + 1);
            }
        }

    }