UnionFind

Disjoint Set Union とも言う

頂点が $n$ 個あり辺のないグラフに対して，以下のクエリを捌くデータ構造

• merge(u,v) ： 頂点 $u,v$ 間に無向辺を張る
• is_same(u,v) ： 頂点 $u,v$ が連結かどうかを返す

Library Checker

きちんとした定義のためにグラフ理論を持ち出したが，グラフだと思わず単に「$u,v$ を同じグループにする」くらいに思っても良い．（じゃんけん列車みたいなイメージ） 辺は追加するだけで削除は出来ない．

例えば is_same に対して都度 BFS 行うような実装が考えられる． なんの工夫もしない場合 merge が $\Theta(1)$ で is_same が $\Theta(m)$ ．

基本アイデア

連結性が同じであればどのようなグラフで状態を管理しても良い

気になっているのは連結性だけなので，以下の二つのグラフは同一視出来る．

管理するグラフは森でよい

森：サイクルのないグラフのこと

連結性だけが大事なのでサイクルは無駄がある．

各木を根付き木にすると「根が同じか」で判定出来る

「同じ連結成分か？」を「根が同じか？」に言い換えられる．