Union-Find / Disjoint Set

1정의#

유니온 파인드(Union-Find), 또는 서로소 집합(Disjoint Set Union, DSU)은 원소들을 겹치지 않는 집합들로 분리해 관리하는 자료구조다.

두 연산을 지원한다.

• Find(x): x가 속한 집합의 대표 원소(루트)를 반환한다.
• Union(x, y): x가 속한 집합과 y가 속한 집합을 하나로 합친다.

2구현#

각 원소 x에 대해 parent[x]를 관리한다. 루트는 parent[x] == x인 원소다. 초기에는 모든 원소가 자기 자신을 부모로 가진다.

int parent[N];

void init(int n) {
    for (int i = 0; i < n; i++) parent[i] = i;
}

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

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) parent[x] = y;
}

find는 부모를 따라 올라가며 루트를 찾는다. unite는 두 루트 중 하나를 다른 하나의 자식으로 붙인다.

같은 집합인지 확인은 find(x) == find(y)로 한다.

3시간 복잡도#

최적화 없이는 트리가 일렬 체인이 될 수 있다.

예시: unite(0, 1), unite(1, 2), ⋯, unite(n-2, n-1)을 순서대로 수행하면 0 → 1 → 2 → ⋯ → n−1 형태의 체인이 만들어진다. 이때 find(0)은 n−1번 포인터를 따라가야 한다.

연산	최악 시간 복잡도
Find	O(n)
Union	O(n)