Union-Findとは何ですか？

素集合（互いに重ならない集合）を効率的に管理するデータ構造。要素がどのグループに属するかの判定や、グループの統合をほぼO(1)で行える。

Union-Findのポイントは？

「Find（どのグループ？）」と「Union（グループ統合）」の2操作がメイン。経路圧縮とランクによる併合で、ほぼ定数時間の超高速処理を実現。グラフの連結成分判定やクラスカル法（最小全域木）で大活躍。競技プログラミングでは頻出の基本データ構造として知られる

【ユニオンファインド】

💡 「キミとボク、同じチームだよね？」を一瞬で答えるデータ構造

📌 このページのポイント

Union-Find のツリー構造と経路圧縮のイメージ

ひよこ

Union-Findって何に使うの？

ペンギン先生

たとえば学校のクラス替えを想像してみて。「AさんとBさんは同じグループ？」を一瞬で答えられて、「CさんのグループとDさんのグループを合体！」もすぐできる仕組みだよ

ひよこ

FindとUnionって名前のまんまなんだね。でもリストとかで管理するだけじゃダメなの？

ペンギン先生

素朴にやると全員のグループ番号を書き換えるのにO(n)かかっちゃう。Union-Findはツリー構造を使って、代表者（根）を辿るだけでグループが分かるから圧倒的に速いんだよ

ひよこ

ツリーが深くなったら遅くなりそうだけど…

ペンギン先生

そこで「経路圧縮」というテクニックを使うんだ。Findのときにたどった要素を全部直接根につなぎ直す。次からは一発で根にたどり着けるようになるよ

ひよこ

賢い！実際どんな場面で使われるの？

ペンギン先生

代表的なのはクラスカル法という最小全域木アルゴリズムだね。辺を追加するとき「この辺の両端は同じ連結成分？」をUnion-Findで高速判定するんだ。SNSの友達ネットワーク分析やネットワークの接続判定にも使われるよ

ひよこ

計算量はどのくらい速いの？

ペンギン先生

経路圧縮とランクによる併合を両方使うと、m回の操作でO(m α(n))になる。α(n)はアッカーマン関数の逆関数で、実質的に4以下。つまりほぼ定数時間と思っていいレベルだよ

まとめ：ざっくりこれだけ覚えればOK！

「Union-Find」って出てきたら「グループ分けを超高速で管理する仕組み」と思えればだいたいOK！

📖 おまけ：英語の意味

「Union-Find (Disjoint Set Union)」＝和集合-検索（素集合の統合）

💬 Union（統合する）とFind（見つける）という2つの操作がそのまま名前になっているよ。別名の Disjoint Set Union（DSU）は「互いに重ならない集合の統合」という意味だよ