ランクによるUnionと逆アッカーマン境界
ランクに基づくunionを追加して木を平坦に保ち、2つの最適化を組み合わせると償却計算量がO(alpha(n))、実質的に定数時間になる理由を理解します。
「ランクによるUnionと逆アッカーマン境界」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
ランクがないと木が高くなる理由
通常の経路圧縮は、走査の後には高い木ができるのを防ぎます。しかし、最初の union 操作中に、常に大きい木のルートを小さい木の下に付けると、依然として高い木を作れてしまいます。ランクによる併合は、木の高さの上限（ランク）を追跡し、常に浅い木を深い木の下に付けることで、この問題を解決します。
ランクは正確な高さではありません。経路圧縮によって、ランクより実際の高さが低くなることがあるためです。ただし、ランクは高さの上限です。深い木を新しいルートとして維持すると、ランクが増えるのは同じランクの木を 2 つ併合したときだけになるため、最大ランクを O(log n) に抑えられます。
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ランクによる併合の 3 つのケース
ルートが px と py の 2 つの成分を併合するとき、ランクに応じて 3 つのケースがあります。
- rank[px] > rank[py]：py を px の下に付ける — px のランクは変わらない
- rank[px] < rank[py]：px を py の下に付ける — py のランクは変わらない
- rank[px] == rank[py]：py を px の下に付ける（逆でも可） — 新しいルートのランクが 1 増える
ランクが増えるのは、同じランクの場合だけです。つまり、ランク n の木には少なくとも 2^n 個のノードが必要であり、最大ランクは O(log n) です。これにより、経路圧縮がなくても find の経路を短く保てます。
# 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))経路圧縮とランクによる併合の組み合わせ
経路圧縮とランクによる併合を同時に使うと、1 操作あたりの償却時間は O(alpha(n))（逆アッカーマン関数）まで下がります。実用上のあらゆる入力サイズ（2^65536 まで）では、alpha(n) は高々 4 です。これは実質的に定数時間です。
経路圧縮は走査後に木を下から上へ平坦化し、ランクによる併合は併合中に木が上から下へ高くなるのを防ぎます。この 2 つは相補的です。ランクが初期の深さを抑え、圧縮が最初の走査後にその深さを取り除きます。
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逆アッカーマン関数を理解する
アッカーマン関数 A(m, n) は非常に速く増加し、すべての原始再帰関数より速く増加します。その逆関数である alpha(n) は、A(m, m) >= n を満たす最小の m として定義されます。アッカーマン関数が非常に速く増加するため、alpha(n) の増加は想像できないほど緩やかです。
n = 10^80（観測可能な宇宙にある原子の数）であっても、alpha(n) はまだ 4 にすぎません。これが、両方の最適化を使った DSU が、実用上のあらゆる状況で実質的に定数時間とみなされる理由です。alpha(n) が 5 を超えるほど大きな現実の問題に遭遇することはありません。
# 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.')ランクとサイズ：どちらを使うべきか
ランクによる併合の代わりにサイズによる併合を使うこともできます。常にサイズの小さい木をサイズの大きい木の下に付けます。どちらの方法でも、木の高さは O(log n) になります。サイズは正確な個数であるため、ランクよりも考え方が簡単なことがよくあります。ランクは上限であり、圧縮後の実際の高さを反映しない場合があるためです。
面接では、どちらの方法でも問題ありません。サイズによる併合には、追加のコストなしで成分サイズも得られるという利点があり、多くの問題で役立ちます。ランクによる併合は理論的にはやや洗練されており、逆アッカーマン関数による上限を示した Tarjan の元の証明にも対応しています。
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) に保たれる理由
ランク r の DSU の木には、少なくとも 2^r 個のノードが含まれることを帰納法で証明できます。基底の場合、ランク 0 は 1 個のノードを意味します（2^0 = 1）。帰納段階では、ランク r が増えるのは、ランク r-1 の木を 2 つ併合したときだけです。帰納法の仮定により、各部分木には少なくとも 2^(r-1) 個のノードがあるため、併合後の木には少なくとも 2 × 2^(r-1) = 2^r 個のノードがあります。
ランク r の木には少なくとも 2^r 個のノードがあり、全ノード数は n なので、最大ランクは高々 log₂(n) です。つまり、経路圧縮なしの find は 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 テンプレート
競技プログラミングや面接では、短く正しく、あらゆるエッジケースに対応できる、実績のある DSU テンプレートが必要です。以下のテンプレートでは、パスハルビング（1 回の走査による圧縮）とサイズによる併合を組み合わせています。この組み合わせは素早く入力しやすく、再帰も完全に避けられます。
必ず parent[i] = i および size[i] = 1 に初期化してください。また、find の後は、ルートの size が成分全体のサイズを表すことを覚えておきましょう。size[x] を直接使わず、必ず size[find(x)] を使ってください。
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)) # 3DSU では不十分な場合
DSU は集合の併合をサポートしますが、集合を 2 つに分割して元に戻すことはサポートしません。グループの結合と分離の両方が必要な問題では、別のデータ構造（link-cut tree など）が必要です。また、DSU は各グループの要素を標準では保持しないため、そのために追加の隣接リストや辞書が必要になります。
さらに、標準的な DSU は変更なしでは重み付き辺をサポートしません（重み付き DSU はより高度なバリエーションです）。連結したノード間の最小コスト経路のような問題には、Dijkstra や BFS のほうが適しています。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 の比較
BFS/DFS と DSU はどちらも静的な連結性クエリを解決しますが、それぞれに異なる強みがあります。BFS/DFS は O(V + E) で実行でき、ノード間の実際の経路を見つけられます。DSU は、辺の集合が段階的に増えていく場合に、多数の連結性クエリへクエリごとにほぼ O(1) で回答できます。これは、辺が一度に 1 本ずつ追加される オンライン アルゴリズムに最適です。
すべての辺を最初から受け取り、連結性だけが必要であれば、どちらを使っても構いません。辺が動的に追加され、新しい辺が追加されるたびに連結性クエリへ回答する必要がある場合は、DSU が明らかに適しています。最短経路も必要な問題では、BFS を使ってください。
# 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 を使った最小全域木
最小全域木を求める Kruskal's algorithm は、DSU を直接使用します。すべての辺を重みの順に並べ替え、端点が異なる連結成分に属している場合（つまり、閉路を作らない場合）に、その辺を貪欲に追加します。DSU により、閉路の判定をほぼ O(1) で行えます。結果は n-1 本の辺からなる MST です。
これは DSU の強力さを示す典型的な例です。単純な方法では O(E × V) かかる閉路判定を、O(E × alpha(n)) の処理に変えられます。さらに、辺のソートに E log E の時間がかかるため、Kruskal の全体の計算量は O(E log E) です。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)ロールバック付き DSU: オフライン連結性
標準的な DSU は取り消し操作をサポートしていません。しかし、ロールバック付き DSU（履歴付き DSU とも呼ばれます）はサポートしています。取り消しが難しいパス圧縮の代わりにランクによる union だけを使い、各 union をスタックに記録します。ロールバックする際は、スタックから取り出して parent と rank を復元します。これにより、辺の追加と削除が行われるオフライン動的連結性問題を解けるようになります。
これは標準的な面接ではほとんど見かけない高度な変種ですが、重要な不変条件がパス圧縮ではなくランクによる union であることを示しています。パス圧縮を使わない場合、各 find は O(log n) です。一方、ロールバック時のスタック操作は O(1) なので、全体では操作 1 回あたり O(alpha(n)) ではなく O(log n) になります。
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理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、ランクによる union では常に浅い木を深い木の下に結合すること、同じランクの木同士を結合するときだけランクが増加し、木の高さが O(log n) に抑えられること、そしてパス圧縮とランクによる union を組み合わせると O(alpha(n)) 償却、つまり実質的に定数時間を達成できることを学びました。次は、最適化された DSU を使って、グラフにおける冗長な接続と閉路検出に取り組みます。
よくある質問
「ランクによるUnionと逆アッカーマン境界」レッスンは無料ですか？
はい。「ランクによるUnionと逆アッカーマン境界」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「ランクによるUnionと逆アッカーマン境界」で何を学びますか？
ランクに基づくunionを追加して木を平坦に保ち、2つの最適化を組み合わせると償却計算量がO(alpha(n))、実質的に定数時間になる理由を理解します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「ランクによるUnionと逆アッカーマン境界」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 経路圧縮付きDSU
- ランクによるUnionと逆アッカーマン境界
- Redundant Connectionと閉路検出
- Accounts Mergeと連結成分