[C++] Union-Find 구현

정의

• 상호 배타적 집합(서로소 집합)(Disjoint-Set)을 표현할 때 사용하는 그래프 알고리즘
  • Disjoint-set은 공통 원소가 없는 상호 배타적인 부분집합들로 나눠진 원소들에 대한 정보를 표현하는 자료구조
• 집합을 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어짐
  • Union(합치기): 두 원소가 속한 집합을 하나로 합친다.
  • Find(찾기): 해당 원소가 속한 집합을 반환한다.
• 핵심은 각각의 집합을 하나의 트리로 나타내는 것
• Union-Find를 사용하면 특정 노드가 어느 집단에 속해 있는지 알 수 있다.
• 트리의 구조를 사용해서 시간복잡도가 평균적으로 O(log N)이지만, 편향될 경우 O(N)이 될 수 있다.
  • 경로 압축(Path Compression), Rank기반 연산을 통해 최적화하여 상수에 가깝게 만들 수 있음
  • 경로 압축: Find는 Depth가 낮을 수록 유리하다는 점을 이용해서 매번 Find할 때, Depth가 2 이상이면 path compression 수행. Root node를 원하는 값으로 강제할 수 있다는 특징
  • Union by rank: rank에 트리의 높이(rank)를 저장하고 항상 높이(rank)가 더 낮은 트리를 높은 트리 밑에 넣음. Union 과정을 역추적할 수 있다는 특징(Roll-back 가능)

#include <iostream>
#include <vector>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    // Constructor: 초기화, n개의 원소가 각각 독립된 집합으로 시작함
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);  // 초기에는 모든 집합의 랭크가 0
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 각 원소는 자기 자신을 부모로 가짐 (자기 자신이 루트)
        }
    }

    // Find: 경로 압축을 사용하여 집합의 대표자를 찾음
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 경로 압축
        }
        return parent[x];
    }

    // Union: 두 집합을 합침, 랭크를 기준으로 트리의 높이를 최소화
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;  // 높이가 더 낮은 트리를 높이가 더 높은 트리에 연결
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;  // 랭크가 같을 때는 한쪽의 랭크를 증가시킴
            }
        }
    }

    // 같은 집합에 속하는지 확인
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};