Union-Findアルゴリズム
以下のUnion-Find操作を高速に行うアルゴリズム
Union：グループを併合する操作
Find：所属するグループを検索する操作
参考
AtCoder公式
ネット上でのUnion-Findに関する情報
習得の流れ
座学：Union-Findの解説動画視聴
非常に丁寧でわかりやすい。Union-Findはとっつきにくい感じがあるが、動画を観ることですんなりと導入できる
演習：C++で写経
ATC
座学：種々のネットや書籍でのUnion-Findの解説を確認
Union-Findの実装にはいろいろなパターンがあり、データの持ち方が微妙に違う
螺旋本、蟻本でも解説あり
AtCoder公式動画の実装が一番美しい気がする
演習：Rustで実装
ATC
理解
木構造で表現するデータ構造であるが、木構造の形がUnion処理によってどう変化するかが最初はイメージしずらい
初期値はすべての要素が１個ずつ独立した状態
クエリに応じて、これを併合していく
木のサイズが小さい方を大きい方にくっつける
これが重要
根を検索することで所属するグループを判定する
この根の検索'(find)処理時に経路縮約も行う
ならし計算量が$ O(N)以下になり、アッカーマン関数の逆関数になるらしい。メッチャ小さい関数らしい。
グループのサイズの表現をしていない例もあるがAtCoder公式は圧巻
なんと親ノード情報のベクトルに組み込む！
親ノードがある子ノードの場合、普通に親ノード番号を要素に入れる
そして根ノードの場合、親はいないので、そこにグループのサイズを入れる
ただしサイズを負の値にして入れる
こうすることでノード番号と区別される！
多くの例では根は自分自身を指すような実装になっている
こういう詰めの部分まで学べるのでAtCoder公式動画は観たほうが学習効率高そう
Union-Findでは分割はできない。重要な制約。
経路縮約しないで木の深さ（ランク）をもっておくような工夫もあるよう。
言葉の整理
Union-Find周りの単語は表記ゆれが結構あります。pyteyonさんが整理してくれています。ありがとうございます。 素集合データ構造＝Union-Find 木
各集合の代表＝木の「根」＝グループの代表
素集合を分割したもの＝素集合＝集合＝木＝グループ
木構造として保持されている（分割された）集合を「グループ」，「集合」，「木」という言葉を使って簡潔に書いてある記事がいくつか見られました．「グループに属しているかどうか」という記述は Union-Find の操作のイメージがしやすいですし，「木に属しているか」という記述は Union-Find の実装をイメージしやすくなります．どの表現がしっくりくるかというのは人により違います
複数の木をまとめて表現する言葉として「森」も出てきたりします。
実装例