Union-Find（素集合データ構造）
要素を グループに併合し、2 つが同じグループかを高速に判定するデータ構造です。
0
union 操作の列
グループ数
—
最大グループのサイズ
—
グループの森（矢印＝親、根がグループの代表）
連結判定（find の結果でリアルタイム更新）
Union-Find（素集合データ構造）は 2 つの操作だけを持ちます ──
union(a,b)：a と b のグループを併合。find(x)：x の属するグループの代表（根）を返す。
各要素は「親」を 1 つ持ち、親をたどった先の根がグループの代表。同じ根なら同じグループです。
2 つの工夫で高速化します：併合時に小さい木を大きい木の下につける（union by size）／ find のたびに通った要素を根に直接つなぎ直す（経路圧縮）。これで木が平たく保たれます。
用途：クラスカル法（最小全域木）、ネットワークの連結判定、画像の領域分割など。
各要素は「親」を 1 つ持ち、親をたどった先の根がグループの代表。同じ根なら同じグループです。
2 つの工夫で高速化します：併合時に小さい木を大きい木の下につける（union by size）／ find のたびに通った要素を根に直接つなぎ直す（経路圧縮）。これで木が平たく保たれます。
用途：クラスカル法（最小全域木）、ネットワークの連結判定、画像の領域分割など。
いまの操作
ここがポイント
- 同じグループかの判定は 「根が同じか」を見るだけ。
- すでに同じグループの 2 要素を union しても何も起きない（スキップ）。
- union by size ＋ 経路圧縮で、1 操作あたりほぼ定数時間（厳密にはアッカーマン関数の逆数）。