Union by Size

1정의#

크기 기반 합치기(Union by Size)는 두 집합을 합칠 때 항상 작은 트리를 큰 트리 아래에 붙이는 기법이다.

2구현#

int parent[N], sz[N];

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

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) return;
    if (sz[x] < sz[y]) swap(x, y);
    parent[y] = x;
    sz[x] += sz[y];
}

sz[x]는 x가 루트인 집합의 크기를 나타낸다. 루트가 아닌 노드의 sz는 의미 없는 값이다.

3시간 복잡도#

find의 최악 시간 복잡도는 O(log n)이다.

4증명#

4.1보조 정리#

깊이가 d인 노드를 포함하는 트리의 크기는 2^d 이상이다.

d에 대한 귀납법을 사용한다.

기저 (d = 0): 루트 노드의 깊이는 0이고 트리 크기 ≥ 1 = 2⁰이다.

귀납 (d → d+1): 깊이 d+1인 노드 v를 생각한다. v의 깊이가 d에서 d+1로 증가한 시점에 v의 트리(크기 s₁)가 더 큰 트리(크기 s₂ ≥ s₁)에 흡수되었다. 귀납 가설에 의해 s₁ ≥ 2^d이므로, 합친 트리의 크기 s₁ + s₂ ≥ 2s₁ ≥ 2^d+1이다. ■

---

결론: 트리 크기 ≤ n이므로 2^d ≤ n, 따라서 d ≤ ⌊log₂ n⌋이다. find는 O(log n)이다.