PythonでUnion-Find（素集合データ構造）を実装する方法【初心者向け解説】
Union-Find（素集合データ構造）は、要素をグループに分けて管理し、効率的に統合や検索を行うデータ構造です。グラフ理論やネットワーク解析でよく使用され、競技プログラミングでも頻出のアルゴリズムです。
Union-Findとは
Union-Findは以下の操作を効率的に実行できるデータ構造です：
- Find操作: 要素がどのグループに属するかを調べる
- Union操作: 2つのグループを統合する
主な用途として、グラフの連結成分の判定、最小全域木の構築、動的連結性の管理などがあります。
基本的なUnion-Find実装
最もシンプルなUnion-Findの実装例：
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
return self.find(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
def same(self, x, y):
return self.find(x) == self.find(y)
# 使用例
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
print(uf.same(0, 1)) # True
print(uf.same(0, 2)) # False
最適化されたUnion-Find実装
パス圧縮とランク併合による高速化：
class OptimizedUnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * 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:
px, py = py, px
self.parent = px
if self.rank[px] == self.rank:
self.rank[px] += 1
実践的な活用例
グループ数を数える
class UnionFindWithCount:
def __init__(self, n):
self.parent = list(range(n))
self.groups = 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
self.groups -= 1
def group_count(self):
return self.groups
# 使用例
uf = UnionFindWithCount(6)
uf.union(0, 1)
uf.union(2, 3)
print(uf.group_count()) # 4
グラフの連結性判定
def is_connected(n, edges):
uf = UnionFind(n)
for x, y in edges:
uf.union(x, y)
root = uf.find(0)
return all(uf.find(i) == root for i in range(n))
# 使用例
edges = [(0, 1), (1, 2), (3, 4)]
print(is_connected(5, edges)) # False
計算量と特徴
Union-Findの計算量（最適化後）：
- Find操作: O(α(n))
- Union操作: O(α(n))
ここでα(n)はアッカーマン関数の逆関数で、実用的にはほぼ定数時間と考えて問題ありません。
まとめ
Union-Findは効率的なグループ管理を可能にする重要なデータ構造です。基本実装から最適化技法まで理解することで、様々なアルゴリズム問題に応用できます。特にグラフ問題や動的連結性が必要な場面で威力を発揮します。
■プロンプトだけでオリジナルアプリを開発・公開してみた！！
■AI時代の第一歩！「AI駆動開発コース」はじめました！
テックジム東京本校で先行開始。
■テックジム東京本校
「武田塾」のプログラミング版といえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
より早く、より安く、しかも対面型のプログラミングスクールです。
＜短期講習＞5日で5万円の「Pythonミニキャンプ」開催中。
＜月1開催＞放送作家による映像ディレクター養成講座
＜オンライン無料＞ゼロから始めるPython爆速講座
