素集合データ構造
素集合森は考案されてからよく使われていたが、上限(そして限定的な下限)がアッカーマン関数の逆関数であることを証明したのはロバート・タージャンだった。それまで、操作毎の時間の上限はジョン・ホップクロフトとジェフリー・ウルマンが証明した O(log n) とされていた。log は重複対数であり、これも増加の遅い関数である(ただし、アッカーマン関数の逆関数ほどではない)。タージャンと van Leeuwen はより効率的なワンパスの Find のアルゴリズムも考案している。
2007年、ACM SIGPLAN の Workshop on ML において、Sylvain Conchon と Jean-Christophe Filliâtre が素集合森データ構造の永続版を発表した。これは構造の以前のバージョンを効率的に保持するもので、計算機支援証明システムCoqを使って形式的に正しさが証明されている。
素集合森 (disjoint-set forest) はそれぞれの集合を木構造で表したデータ構造で、各ノードには親ノードへの参照がある。1964年、Bernard A. Galler と Michael J. Fischer が考案したが、詳細な解析にはその後何年かかかった。
素集合森では、各集合の代表は木構造の根となる。Findは親ノードへのリンクを根に到達するまでたどっていく。Unionは2つの木構造を1つにする操作であり、どちらかの根が全体の根となる。以下に素集合森の実装例を擬似コードで示す。
この素朴な実装では、連結リストを使った場合と変わらない。なぜなら、木構造の平衡が保たれないからである。しかし、これを改善する方法が2つある。
第一の方法は union by rank と呼ばれ、Union操作で常に大きい木の方が全体の根になるように連結するものである。木の大きさを評価するにはrank を用いる。これは、1要素の木の rank を 0 とし、同じ rank r の木を連結したとき、全体の根とした方の木の rank を r+1 とするものである。このようにするだけで、MakeSet、Union、Find 操作の償却実行時間は O ( log  n ) {\displaystyle O(\log n)} となる。改良した MakeSet と Union の擬似コードは以下のようになる。
第二の改善は path compression と呼ばれ、Find操作を行ったときに構造を平坦化するものである。
素集合データ構造は集合の分割をモデル化したもので、例えば無向グラフの連結成分などに対応する。したがって、2つの頂点が同じ成分に属するかどうかを調べたり、新たな辺を追加することで閉道となるかを調べるのに利用できる。
Boost Graph Library では、Incremental Connected Components 機能の実装に素集合データ構造を使っている。また、グラフの最小全域木を求めるクラスカル法の実装にもこれを使っている。
なお、素集合森の実装では削除ができない点に注意されたい。上述した2つの改良を施しても削除は容易ではないが、削除に対応したもっと複雑な手法が既に設計されている。