230209 유니온 파인드, Union-Find or Disjoint-Set

효율적으로 항목을 분리된 집합으로 그룹화하는 것을 다루는 알고리즘
유니온 파인드(Union-Find) 또는 디스조인트-세트(Disjoint-Set) 데이터 구조를 사용하여 효율적인 해결이 가능

• union 연산은 두 집합을 하나의 집합으로 합침
• find 연산은 주어진 항목이 어느 집합에 속하는지 판별

예시

class UnionFind {
    int[] parent;
    int[] size;
    int count;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

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

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] > size[rootY]) {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            } else {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            }
            count--;
        }
    }

    public int count() {
        return count;
    }
}