Union-Findとは何か、どこで使われるのか？

Question

Accepted Answer

**Union-Find**（素集合データ構造）は要素の分割を**互いに素な集合**として追跡し、**find**（xはどの集合に属するか？）と**union**（2つの集合をマージ）という2つのほぼO(1)操作をサポートしています。**接続性**のクエリに優れています。

## アイデア

各集合は代表根を持つツリーです。**経路圧縮**と**ランク/サイズによる統合**により、操作はほぼ定数の**償却**時間で実行されます（逆アッカーマン、α(n)）。

## 例

```python
class UnionFind:
    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]]  # compress
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # attach smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## 計算量

- **find / union:** O(α(n)) ≈ O(1)償却。**空間:** O(n)。

## 応用例

- **クラスカルのMST** — エッジ追加時のサイクル検出。
- **連結成分** / 動的接続性。
- **無向グラフのサイクル検出**。
- **浸透**, 画像セグメンテーション、アカウント/ネットワークマージ。

## 落とし穴

経路圧縮とランク/サイズによる統合がなければ、ツリーはO(n)チェーンに劣化します。集合の効率的な*分割*はサポートしていません。

## なぜ重要なのか

Union-Findは「この2つのものは接続されているか？」という質問にほぼコストなしで大規模に答えます。

クラスカルのMST内部のエンジンであり、多くのグラフおよびクラスタリングアルゴリズムのコア部分です。

その2つの最適化は、小さな構造的なトリックがいかにして準定時間のパフォーマンスをもたらすかを示す印象的な教訓です。