Overview
Union-Findは、素集合データ構造というグラフの連結成分の管理や集合の併合・判定を高速に行うためのデータ構造とそれを操作するアルゴリズム。
1.Union Findの基本
2.Union Findの特徴
3.典型問題を解いてみる
1. Union Findの基本
要素をいくつかのグループ（集合）に分け、以下の操作を効率的に行う。
- Find: 要素が属する集合の代表（根）を求める
- Union: 2つの集合を1つに併合する
- Same: 2つの要素が同じ集合に属するかを判定する
これらの操作を効率的に行うために、木構造を用いて各集合を管理します。
＜基本実装＞
class UnionFind:
def __init__(self, n):
self.parent = [-1] * n # 各要素の親。-1は根を示す。
self.size = [1] * n # 各集合のサイズ。
def find(self, x):
if self.parent[x] == -1:
return x # xが根の場合
self.parent[x] = self.find(self.parent[x]) # 経路圧縮
return self.parent[x]
def unite(self, x, y):
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return False # すでに同じ集合
# サイズの大きい方に小さい方を併合
if self.size[x_root] < self.size[y_root]:
x_root, y_root = y_root, x_root
self.parent[y_root] = x_root
self.size[x_root] += self.size[y_root]
return True
def same(self, x, y):
return self.find(x) == self.find(y)
def get_size(self, x):
return self.size[self.find(x)]
2. Union Findの特徴
特徴
- 高速な操作: 経路圧縮とランク（またはサイズ）による併合を組み合わせることで、ほぼ定数時間で操作が可能
- 簡潔な実装: 少ないコードで実装でき、理解しやすい
- 拡張性: 集合のサイズや最大値などの追加情報を管理する拡張が可能
応用例
- グラフの連結判定: 2つのノードが同じ連結成分に属するかを判定
- サイクル検出: 無向グラフでサイクルが存在するかを判定
- 最小全域木（MST）: クラスカル法で使用
- 連結成分の個数の計算: グラフがいくつの連結成分に分かれているかを求める
3. 典型問題を解いてみる
例題1. Union Findの基本操作
問題: 無向グラフにおいて、2つのノードが連結かどうかを判定する。
回答
class UnionFind:
def __init__(self, n):
self.parent = [-1] * n
def find(self, x):
if self.parent[x] == -1:
return x
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def unite(self, x, y):
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return
self.parent[y_root] = x_root
def same(self, x, y):
return self.find(x) == self.find(y)
n, q = map(int, input().split())
uf = UnionFind(n)
for _ in range(q):
p, a, b = map(int, input().split())
if p == 0:
uf.unite(a, b)
else:
print("Yes" if uf.same(a, b) else "No")
例題2. 友達の友達は友達？
問題: 友達関係の情報から、同じグループに属する人の数を求める。
回答
n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
a, b = map(int, input().split())
uf.unite(a - 1, b - 1)
print(max(uf.get_size(i) for i in range(n)))
例題3. 橋の検出
問題: 無向グラフにおいて、特定の辺を取り除くと連結成分が増えるかを判定する。
回答
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = 0
for i in range(m):
uf = UnionFind(n)
for j in range(m):
if i == j:
continue
a, b = edges[j]
uf.unite(a - 1, b - 1)
if len(set(uf.find(k) for k in range(n))) > 1:
ans += 1
print(ans)
例題4. 都市の連結
問題: 都市間の道路情報から、全ての都市が連結されているかを判定する。
回答
n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
a, b = map(int, input().split())
uf.unite(a - 1, b - 1)
print("Yes" if len(set(uf.find(i) for i in range(n))) == 1 else "No")
例題5. 赤い塗りつぶし
問題: グリッド上で赤く塗られたマスが連結しているかを判定する。
回答
h, w = map(int, input().split())
q = int(input())
uf = UnionFind(h * w)
grid = [[0] * w for _ in range(h)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def index(r, c):
return r * w + c
for _ in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
r, c = query[1] - 1, query[2] - 1
grid[r][c] = 1
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < h and 0 <= nc < w and grid[nr][nc]:
uf.unite(index(r, c), index(nr, nc))
else:
ra, ca, rb, cb = query[1] - 1, query[2] - 1, query[3] - 1, query[4] - 1
if grid[ra][ca] and grid[rb][cb] and uf.same(index(ra, ca), index(rb, cb)):
print("Yes")
else:
print("No")