랭크에 의한 합치기와 역 아커만 상한

랭크가 없으면 트리가 높아지는 이유

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n   # initially all trees have rank 0

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # Attach lower-rank tree under higher-rank tree
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1   # only increases when ranks are equal
        return True

랭크 기준 union의 세 가지 경우

# Illustrating rank behaviour with 8 nodes
dsu_parent = list(range(8))
dsu_rank = [0] * 8

def find(x):
    while dsu_parent[x] != x:
        x = dsu_parent[x]
    return x

def union(x, y):
    px, py = find(x), find(y)
    if px == py: return
    if dsu_rank[px] < dsu_rank[py]:
        px, py = py, px
    dsu_parent[py] = px
    if dsu_rank[px] == dsu_rank[py]:
        dsu_rank[px] += 1

# Build balanced tree step by step
union(0,1); union(2,3); union(4,5); union(6,7)
union(0,2); union(4,6)
union(0,4)
print('Ranks:', dsu_rank)    # max rank <= log2(8) = 3
print('Root of all:', find(0))

경로 압축과 랭크 기준 union 결합

class OptimalDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):                        # path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):                    # union by rank
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

dsu = OptimalDSU(1000)
import random; random.seed(42)
for _ in range(5000):
    dsu.union(random.randint(0,999), random.randint(0,999))
print('Max rank reached:', max(dsu.rank))  # stays very small

역 아커만 함수 이해하기

# Showing how slowly alpha(n) grows
# alpha(n) = smallest m such that A(m,m) >= n
# A(0,n) = n+1
# A(1,n) = n+2
# A(2,n) = 2n+3
# A(3,n) = 2^(n+3) - 3
# A(4,4) = 2^(2^(2^(2^2))) - 3 which is astronomically large

alpha_thresholds = {
    1: 'n=1',
    2: 'n up to 3',
    3: 'n up to about 2048',
    4: 'n up to 10^19728 (far beyond atoms in universe)',
    5: 'essentially unreachable in practice',
}
for k, v in alpha_thresholds.items():
    print(f'alpha(n)={k}: {v}')
print('\nConclusion: DSU operations are effectively O(1) for all real inputs.')

랭크와 크기: 무엇을 사용할까요

class DSUBySize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.size[px] < self.size[py]:
            px, py = py, px       # always attach smaller under larger
        self.parent[py] = px
        self.size[px] += self.size[py]
        return True

dsu = DSUBySize(8)
for u, v in [(0,1),(2,3),(0,2),(4,5),(6,7),(4,6),(0,4)]:
    dsu.union(u, v)
print('Size of giant component:', dsu.size[dsu.find(0)])

증명 개요: 랭크가 O(log n)으로 유지되는 이유

# Verify the 2^rank lower bound empirically
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]
        if self.rank[px] == self.rank[py]: self.rank[px] += 1

n = 32
dsu = DSU(n)
for i in range(n - 1): dsu.union(i, i + 1)
for root in range(n):
    if dsu.find(root) == root:
        r = dsu.rank[root]
        print(f'Root {root}: rank={r}, size={dsu.size[root]}, 2^rank={2**r}')

경쟁 프로그래밍용 DSU 템플릿

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.sz = [1] * n

    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # path halving
            x = self.p[x]
        return x

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if self.sz[x] < self.sz[y]: x, y = y, x
        self.p[y] = x
        self.sz[x] += self.sz[y]
        return True

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return self.sz[self.find(x)]

# Usage
dsu = DSU(10)
dsu.union(0, 5)
dsu.union(5, 9)
print(dsu.same(0, 9))   # True
print(dsu.size(0))       # 3

DSU만으로 충분하지 않은 경우

# DSU is perfect for: connected-components, cycle detection,
# Kruskal's MST, accounts-merge, number-of-provinces

# DSU is NOT suitable for:
# - Splitting/removing edges from a group
# - Finding the actual path between two nodes
# - Storing all members of a group efficiently
# - Directed graphs (without modification)

# Example of storing group members alongside DSU
from collections import defaultdict

class DSUWithMembers:
    def __init__(self, n):
        self.p = list(range(n))
        self.members = defaultdict(set)
        for i in range(n): self.members[i].add(i)

    def find(self, x):
        while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        self.members[px] |= self.members[py]
        del self.members[py]
        self.p[py] = px

연결성을 위한 DSU와 BFS/DFS 비교

# Comparing DSU vs BFS for 1000 nodes, 2000 edges
# After all edges given => BFS works fine
# But with online edge arrival + interleaved queries => DSU shines

from collections import deque

def bfs_connected(graph, src, dst, n):
    visited = set([src])
    q = deque([src])
    while q:
        node = q.popleft()
        if node == dst: return True
        for nb in graph.get(node, []):
            if nb not in visited:
                visited.add(nb); q.append(nb)
    return False

# DSU for same query:
# dsu.same(src, dst) -- O(alpha(n)) amortised
# BFS for same query:
# O(V + E) every time -- not suitable for repeated queries
print('DSU is preferred for repeated connectivity queries.')
print('BFS/DFS is preferred when you also need the actual path.')

연습: DSU를 사용한 최소 신장 트리

def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])  # sort by weight
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py: return False
        if rank[px] < rank[py]: px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]: rank[px] += 1
        return True

    mst_weight = 0
    mst_edges = []
    for u, v, w in edges:
        if union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
    return mst_weight, mst_edges

edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,5)]
w, e = kruskal(4, edges)
print('MST weight:', w)   # 6: edges (1,2,1)+(1,3,2)+(0,2,3)
print('MST edges:', e)

rollback을 사용하는 DSU: 오프라인 연결성

class DSUWithRollback:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.history = []   # stack of (node, old_parent, node2, old_rank)

    def find(self, x):    # NO path compression (cannot undo)
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        # Record state before modifying
        self.history.append((py, self.parent[py], px, self.rank[px]))
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

    def rollback(self):
        py, old_par_py, px, old_rank_px = self.history.pop()
        self.parent[py] = old_par_py
        self.rank[px] = old_rank_px

dsu = DSUWithRollback(5)
dsu.union(0, 1); dsu.union(1, 2)
print('0 and 2 connected:', dsu.find(0) == dsu.find(2))  # True
dsu.rollback()
print('After rollback:', dsu.find(0) == dsu.find(2))     # False

빠른 확인

단원 요약