経路圧縮（path compression）とランクによる併合（union by rank）を備えた、互いに素な集合（union-find）構造とは何ですか？

Question

Accepted Answer

**互いに素な集合（disjoint-set、union-find）** は、要素を重なり合わないグループに分割して管理し、「**この2つは同じグループに属するか？**」および「**2つのグループを併合する**」という問いに **ほぼ定数時間** で答えます。**経路圧縮（path compression）** と **ランクによる併合（union by rank）** を用いると、どちらの操作も **O(α(n))** で動作し、実質的にO(1)になります（αは逆アッカーマン関数です）。

## 仕組み

各集合は木であり、**根（root）** がその集合の代表元です。`find` は根までたどり、`union` は一方の根をもう一方の下にぶら下げます。

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## コード

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
```

| 操作 | 時間（両方の最適化あり） |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## よくある用途

- **クラスカル法によるMST** — 閉路を作らずに連結成分を併合する。
- グラフやグリッドにおける **連結成分**。
- **動的連結性**、およびネットワーク／浸透（percolation）の問題。

## なぜ重要なのか

union-findは、本来であれば繰り返しO(n)のグラフ探索を必要とするグループ化や連結性の問題を解決し、1クエリあたりほぼO(1)にまで圧縮します。

また、集合を逐次的に併合しながら連結性を判定する必要があるときの定番ツールであり、シニアレベルの面接で頻出のトピックです。