크루스칼 MST랑 사이클 판정 공부하다가 유니온-파인드(disjoint set)를 보는데 최적화 두 개가 나와서 질문드려요.


하나는 find 할 때 경로압축이라고 부모를 루트로 바로 당겨주는 거고요.


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


다른 하나는 union 할 때 랭크(또는 트리 크기)가 작은 쪽을 큰 쪽에 붙이는 거잖아요.


def union(a, b):
ra, rb = find(a), find(b)
if ra == rb: return
if rank[ra] < rank[rb]: ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]: rank[ra] += 1


둘을 같이 쓰면 연산당 amortized로 O(α(n)), 역 애커만 함수라 사실상 상수라고 하는데 이게 실감이 잘 안 나요. 하나만 써도 되는 거 아닌가요? 두 개가 각각 뭘 막아주길래 합치면 그렇게까지 빨라지는 건지 설명 부탁드려요.