集合の代表を親リンクで表す
Union-Findは、互いに重ならない集合への所属を管理するデータ構造です。最初は各要素だけの集合を作り、find(x)でxの属する集合の代表を求め、union(x,y)で二つの集合をまとめます。木で実装する場合、各要素は親へのリンクを持ち、根を代表にします。代表が同じなら同じ集合です。根の番号に特別な意味があるとは限らず、併合の方式によって代表が変わることがあります。
接続情報を追加する例
最初に{A}、{B}、{C}、{D}の四集合があるとします。union(A,B)の後は{A,B}、union(C,D)の後は{C,D}です。さらにunion(B,C)を行うと四要素は一つの集合になります。このときAとDの間に直接の辺がなくても、同じ連結成分に属すると判定できます。ただし親リンクは集合を効率よく管理する内部表現であり、入力グラフで実際に与えた辺や、具体的な経路をそのまま保存するものではありません。
木を深くしない二つの工夫
サイズによる併合では、小さい集合の根を大きい集合の根へつなぎます。経路圧縮ではfind中に通った要素を根の近くへ付け替え、次回の探索を短くします。union by rankと呼ぶ高さの目安を使う方式もあります。適切な併合規則と経路圧縮を組み合わせると、一連の操作は逆Ackermann関数α(n)を使う非常に小さい償却時間で処理できます。個々の操作が無条件に最悪O(1)になる、という主張ではありません。
使える問い合わせと使えない問い合わせ
辺を追加していく無向グラフの連結判定や、Kruskal法で閉路を作る辺を避ける判定に使えます。一方、基本形は集合をまとめる操作が中心で、辺の削除によって集合が分裂する動的連結性には、そのまま対応できません。また、集合内の全要素列挙や二点間の経路取得も、基本の親配列だけでは直接の機能ではありません。findは経路圧縮のため内部状態を書き換えることがあるので、並行実行や巻き戻しが必要なら別の設計条件も確認します。