Union-Find (Disjoint Set Union) 자료구조

Union-Find란

Union-Find(Disjoint Set Union, DSU)는 서로소 집합을 효율적으로 관리하는 자료구조입니다.

핵심 연산:

• find(x): x가 속한 집합의 루트(대표 원소) 반환
• union(x, y): x와 y가 속한 두 집합을 합침
• connected(x, y): x와 y가 같은 집합인지 확인

기본 구현

class UnionFind {
    vector<int> parent;
    vector<int> rank;
    int components;

public:
    UnionFind(int n) : parent(n), rank(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i
    }

    // Path Compression: 루트까지 경로의 모든 노드를 루트에 직접 연결
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    // Union by Rank: 낮은 트리를 높은 트리 아래에 붙임
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;  // 이미 같은 집합

        if (rank[rx] < rank[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;

        components--;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
    int  count()                  { return components; }
};

시간 복잡도

Path Compression + Union by Rank를 함께 사용할 때:

• find, unite: 거의 O(1), 정확히는 O(α(n)) — 역 아커만 함수로 사실상 상수

사이클 감지

그래프에 사이클이 있는지 판별합니다.

bool hasCycle(int n, vector<pair<int,int>>& edges) {
    UnionFind uf(n);
    for (auto [u, v] : edges) {
        if (!uf.unite(u, v))
            return true;  // 이미 같은 집합 → 사이클
    }
    return false;
}

크루스칼 알고리즘 (최소 신장 트리)

int kruskal(int n, vector<tuple<int,int,int>>& edges) {
    // edges: {가중치, u, v}
    sort(edges.begin(), edges.end());

    UnionFind uf(n);
    int totalWeight = 0, edgeCount = 0;

    for (auto [w, u, v] : edges) {
        if (uf.unite(u, v)) {
            totalWeight += w;
            if (++edgeCount == n - 1) break;  // MST 완성
        }
    }

    return (edgeCount == n - 1) ? totalWeight : -1;  // -1: 연결 불가
}

네트워크 연결 문제

// n개 노드, m개 쿼리
// 쿼리: 0 u v → u, v 연결
//       1 u v → u, v 같은 집합인지 출력
void solve() {
    int n, m; cin >> n >> m;
    UnionFind uf(n);

    while (m--) {
        int type, u, v; cin >> type >> u >> v;
        if (type == 0) uf.unite(u, v);
        else cout << (uf.connected(u, v) ? "YES" : "NO") << '\n';
    }
}

경로 가중치 Union-Find (Weighted DSU)

집합 간 상대적 관계(거리, 차이)를 함께 저장합니다.

class WeightedUnionFind {
    vector<int> parent;
    vector<long long> weight;  // parent까지의 가중치

public:
    WeightedUnionFind(int n) : parent(n), weight(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    pair<int, long long> find(int x) {
        if (parent[x] == x) return {x, 0};
        auto [root, w] = find(parent[x]);
        weight[x] += w;
        parent[x] = root;
        return {root, weight[x]};
    }

    void unite(int x, int y, long long w) {
        // x와 y의 가중치 차이가 w
        auto [rx, wx] = find(x);
        auto [ry, wy] = find(y);
        if (rx == ry) return;
        parent[rx] = ry;
        weight[rx] = wy - wx + w;
    }
};

정리

• Path Compression + Union by Rank로 O(α(n)) 달성
• 사이클 감지, MST(크루스칼), 연결 요소 수 계산에 핵심적으로 사용
• 경로 가중치 DSU로 상대적 관계가 있는 문제도 처리 가능
• 구현이 간단하고 빠르므로 그래프 문제에서 가장 먼저 검토할 자료구조