経路圧縮付きDSU
経路上のすべてのノードが直接ルートを指すように経路圧縮付きのfindを実装し、償却計算量がほぼO(1)のfindを実現します。
「経路圧縮付きDSU」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
Disjoint Set Union とは
Disjoint Set Union（DSU）は Union-Find とも呼ばれ、互いに素な（重なりのない）集合の集まりを管理するデータ構造です。2 つの基本操作をサポートします。find は要素 x がどの集合に属しているかを調べ、union は x と y を含む集合を統合します。DSU は、時間の経過とともにグループが統合される一方で、分割されることはない動的連結性の問題に適しています。
すべての要素は、最初はそれぞれ独立した集合に属します。辺や関係を処理するにつれて、集合を統合していきます。課題は、これを効率的に行うことです。単純な実装では 1 回の操作に O(n) かかりますが、最適化を施すと償却計算量 O(1) に近づけられます。
# Naive DSU without optimisations
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # each node is its own parent
def find(self, x):
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:
self.parent[px] = py素朴な find の問題
素朴な DSU では、find(x) は自己自身を指すノード（ルート）に到達するまで親の連鎖をたどります。木がバランスしていれば、これは O(log n) です。しかし、常に 2 番目のルートを 1 番目の下にリンクして併合すると、長さ n の連鎖（退化した木）ができ、各 find は O(n) になります。
0→1→2→3→4 の順に併合する場合を考えてみましょう。ノード 0 の find 呼び出しでは、連鎖全体をたどる必要があります。経路圧縮を使うと、find 操作そのもので、訪れたすべてのノードがルートを直接指すように変更されるため、この問題を解消できます。
# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4] => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4] => find(0) takes 1 step
parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
x = parent[x]
steps += 1
print('Root:', x, 'Steps taken:', steps)経路圧縮：一度の再帰走査
経路圧縮は find 操作を変更し、ルートを見つけた後、経路上のすべてのノードがルートを直接指すように更新します。これにより、以降のそれらのノードに対する find 呼び出しは O(1) になります。再帰版では、これを 1 回の走査で簡潔に実現できます。
重要なポイントは、再帰呼び出しからルートが返された後、戻る前に self.parent[x] = root を設定することです。これにより木が平坦化され、検索経路上のすべてのノードがルートを直接指すようになります。これはノードが属する集合を変えるのではなく、今後の検索経路を短くするだけです。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
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:
self.parent[px] = py
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)経路圧縮：2 回の反復走査
経路圧縮の反復版では、2 回の走査を行います。1 回目の走査でルートまで上にたどり、2 回目の走査で経路上のすべてのノードを再訪して、親がルートを直接指すように更新します。これにより再帰スタックのオーバーヘッドを避けられ、Python の再帰制限に近い非常に深い木でも安全に使えます。
再帰版と反復版のどちらでも、正しさは変わりません。find は引き続き同じルートを返します。異なるのは、副作用として親ポインタが更新される点だけです。これにより、以降のそれらのノードに対する find は O(1) になります。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root] # first pass: find root
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root # second pass: compress
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
return True
return False # already connected
dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after find(0):', dsu.parent[:])経路圧縮の償却計算量
経路圧縮だけでも、m 個の操作列に対して、1 操作あたりの償却時間は O(log n) になります。最初に連鎖をたどる find 操作には時間がかかる場合がありますが、その連鎖を平坦化するため、以降のそれらのノードに対する find はすべて O(1) になります。全体の処理量が多くの操作に分散されるためです。
形式的な解析にはポテンシャル関数法を使います。ノードの親までの距離が短くなるたびに DSU のポテンシャルが減少し、その減少分が走査コストを支払います。ランクによる併合を使わない場合でも、経路圧縮だけで償却計算量は O(log n) になり、素朴な O(n) と比べてすでに大幅に改善されます。
# Demonstrating amortised benefit
import time
def build_chain(n):
parent = list(range(n))
for i in range(n - 1):
parent[i] = i + 1 # chain: 0->1->2->...->n-1
return parent
n = 1000
parent = build_chain(n)
# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
root = parent[root]
# Compress
while parent[x] != root:
nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0]) # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')連結成分数のカウント
DSU の一般的な応用の 1 つに、グラフの連結成分数のカウントがあります。components カウンタを n（各ノードにつき 1）に初期化します。異なる 2 つの集合を併合する union が成功するたびに、カウンタを 1 減らします。最後には、カウンタが異なる成分の数を保持しています。
これは、連結性のクエリごとに BFS や DFS を実行するより効率的です。特に、辺が逐次的に到着するオンラインの場合に有効です。DSU は辺がいつ到着しても、各辺をほぼ O(1) の償却時間で処理します。
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.components = 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
self.parent[px] = py
self.components -= 1
return True
dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
dsu.union(u, v)
print('Components:', dsu.components) # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')グラフ問題の DSU：州の数
Number of Provinces 問題では、n×n の隣接行列が与えられ、直接または間接的に接続された都市のグループがいくつあるかを求めます。これはまさに連結成分の問題であり、DSU で簡潔に解決できます。isConnected[i][j] == 1 となるすべての (i, j) の組について反復し、union(i, j) を呼び出します。
すべての接続を処理した後の dsu.components が答えです。未訪問の各ノードから BFS を実行するよりも簡単で高速であり、最初に隣接リストを作成しなくても行列形式をそのまま扱えます。
def find_provinces(isConnected):
n = len(isConnected)
parent = list(range(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:
parent[px] = py
return True
return False
count = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
if union(i, j):
count -= 1
return count
matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix)) # 2: cities {0,1} and {2}経路圧縮のバリエーション：パスハルビング
2 回の走査による圧縮以外に、パスハルビングと呼ばれる、より簡単な 1 回の走査による方法があります。連鎖を上にたどりながら、各ノードが親ではなく祖父ノードを指すようにします。これにより、2 回目の走査を行わずに走査のたびに経路の長さを半分にでき、ランクによる併合と組み合わせると同じ O(alpha(n)) の償却計算量を達成できます。
パスハルビングは、再帰や 2 回目の走査が不要な、すっきりした 1 つのループで実装できるため、競技プログラミングでよく好まれます。各ステップでは self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x] を実行します。
class DSUHalving:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # point to grandparent
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
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))併合後の連結性の確認
2 つのノードが連結している（同じ成分に属している）かを確認するには、find(x) == find(y) を呼び出します。両方が同じルートを返す場合、それらは同じ成分に属しています。これは連結性クエリであり、経路圧縮を使えば償却計算量はほぼ O(1) です。
面接問題では、連結性クエリが union 操作と交互に現れることがよくあります。DSU なら両方をオンラインで処理でき、任意の順序で union とクエリを交互に実行できます。この点が、構造が変化するたびに再実行が必要な BFS/DFS のような静的グラフアルゴリズムとの違いです。
class DSU:
def __init__(self, n):
self.parent = list(range(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:
self.parent[px] = py
def connected(self, x, y):
return self.find(x) == self.find(y)
dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7)) # True: 0-3-7
print(dsu.connected(0, 5)) # False: different components
print(dsu.connected(1, 5)) # True: 1-5DSU 実装でよくある落とし穴
よくある間違いは、find を呼び出した後に parent を誤って変更することです。等しいかどうかを確認する前に、必ず両方の要素に対して find を呼び出してください。そうしないと、ノードとそのルートを誤って比較してしまう可能性があります。また、両方の要素がすでに同じルートを共有している場合、union は何もしないべきであることを忘れないでください。
Python では、再帰版の find で大きな連鎖を処理すると、再帰の深さ制限（デフォルトは 1000）により RecursionError が発生することがあります。反復による 2 回の走査の版を使うか、sys.setrecursionlimit で制限を増やすか、反復的なパスハルビングを使って深い再帰を完全に避けてください。
import sys
sys.setrecursionlimit(10000) # needed for large recursive DSU
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
# Safe iterative path compression
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # already same component — do nothing
self.parent[px] = py
return True
dsu = DSU(5)
print(dsu.union(0, 1)) # True: merged
print(dsu.union(0, 1)) # False: already merged — no double-countingDSU によるサイズの追跡
問題によっては、ルートだけでなく各成分のサイズが必要になります。すべて 1 で初期化した size 配列を追加します。2 つの成分を併合するときは、小さいルートのサイズを大きいルートに加えます。これにより、どの union の後でも成分サイズを O(1) で問い合わせられます。
サイズの追跡はサイズによる併合（ランクによる併合に代わる方法）の基礎でもあります。常に小さい木を大きい木のルートの下に付けます。これにより木の高さが O(log n) に保たれ、ランクによる併合と同じ漸近的な保証が得られます。
class DSUWithSize:
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
if self.size[px] < self.size[py]:
px, py = py, px # attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
def get_size(self, x):
return self.size[self.find(x)]
dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0)) # 3
print('Size of component containing 3:', dsu.get_size(3)) # 2
print('Size of component containing 5:', dsu.get_size(5)) # 1理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、DSU は find と union の操作で素集合を管理すること、経路圧縮は、たどったすべてのノードがルートを直接指すようにして木を平坦化すること、そしてこれにより find の償却性能がほぼ O(1) になることを学びました。次はランクによる併合を見ていきます。これは木を上から下まで浅く保ち、逆アッカーマン関数による計算量の上限を実現します。
よくある質問
「経路圧縮付きDSU」レッスンは無料ですか？
はい。「経路圧縮付きDSU」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「経路圧縮付きDSU」で何を学びますか？
経路上のすべてのノードが直接ルートを指すように経路圧縮付きのfindを実装し、償却計算量がほぼO(1)のfindを実現します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「経路圧縮付きDSU」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。