Interactive
Union-Find可視化
Union-Find（素集合データ構造）は、互いに素な集合の集まりを森（複数の木）で表し、find(x)（xの属する集合の代表元＝根を返す）とunion(x, y)（2つの集合を1つに併合する）を高速に処理します。 固定10要素（0〜9）で、経路圧縮（findで辿ったノードを直接根につなぎ替える）とunion by rank（低い木を高い木の下につなぐ）を、それぞれステップ再生できます。
find（経路圧縮つき）
現在の集合数: 8
union（union by rankつき）
∪
根（集合の代表）非根ノードこのステップで注目
1 / 1
find・根に到達
初期状態（2∪3, 5∪6 を実行済み）
ここから好きな要素でfindやunionを試せます。
ここが分かる
- findは読み取り専用に見えて経路圧縮で構造そのものを書き換える——一度根まで辿った要素は、次からどんなに深い場所にいても1段で根に着く。
- unionはunion by rank単体でも木の高さをO(log n)に抑えるが、経路圧縮と組み合わせるとm回の操作の合計がO(m α(n))まで縮む。α(n)は逆アッカーマン関数で、現実的なnでは4以下の事実上の定数。
- rankは「木の高さの上界の目安」であって実際の高さそのものではない——経路圧縮で木が平たくなってもrankを更新し直す必要はなく、それでも計算量の保証は崩れない。
- 「2つの要素が同じグループか」は
find(x) === find(y)で判定できる——Kruskal法の閉路検出や連結成分の数え上げなど、動的な連結性を問う問題の定番ツール。