素集合データ構造

disjoint-set data structure

データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造

Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。

Union: 2つの集合を1つに統合する。

これら2つの操作をサポートしているため、素集合データ構造は「Union-Findデータ構造」あるいは「Merge-Find集合」とも呼ばれる。これら以外の重要な操作として MakeSetがある。これは、与えられた1つの要素だけを格納した集合（シングルトン）を作成する。これら3つの操作により、様々な実用的分割問題を解くことができる（「応用」の節を参照）。