互いに素な集合(Disjoint-set・Union-find)データ構造2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用いて表現され、各ノードが集合に含まれる元になります。Tree工夫をすれば、集合に新たな要素を加えるor集合同士をまとめる操作や、同じ集合に要素があるかを判定する操作を\(O(logn)\)よりも高速に行うことができます。データを互いに素な集合(素集合系)にして管理するためのデータ構造です。以下の操作が行えます。xを含む木の根(root)を求める。木の根を代表点(representative)と言ったりする。同じ木(集合)にあるのかを、根が同じかで判定する1つの木が、1つの集合を表しています。工夫をすれば、木(集合)同士の併合や、同じ集合に含まれているかの判定は高速にできます。一度まとめた集合を分割したり、ノードを削除したりするのにはあまり向いていません。なにも工夫しない場合における操作を詳しく見ておきましょう。根とした木をつくることができます。makeTree(2)では以下のようになります。parents[i]:=iの親}findRoot(x)findRoot(x)によって、xを含む木の根、つまり代表となる点を求めます。以下のような木に対してfindRoot(6)を行った場合は、代表点である4を返します。findRoot(parent[x]);}union(x,y)2つの木をつなげることを考えましょう。以下の図の時を例に考えます。よって、3を含む木と5を含む木を1つにまとめます。出来上がる木の代表点は、もともとの木の2つの代表点のどちらかになるようにしましょう。先程の実装のように、普通に木を作って何も考えずに併合することを繰り返すと、以下のように木が長くなってしまう可能性があります。応じた時間がかかってしまい効率が悪くなります。これを防ぐためには、主に2種類の手法を組み合わせて使います。計算量が\(O(logn)\)まで高速化できます。左図のような木について、findRoot(9)をすることを考えます。下から代表点である2へとたどるついでに、途中の点を全て2へと繋いでしまえば、右図のように木の高さが低くなります。findRoot(x)を変更して、自身の親を、木の根に更新するコードにしましょう。parents[x];}この工夫により、計算量が\(O(n)\)から\(O(logn)\)になります。よって、2を含む木と5を含む木を1つにまとめることを考えましょう。この時、代表点2の木と代表点5の木のどちらをどちらに繋げるのかで効率が変わってきます。木の高さが低い方を高い方へ繋げる木のサイズ(ノード数)が小さい方を大きい方へ繋げるどちらの戦略であっても、今回は以下のようになります。逆のつなげ方をすると、以下のように木の高さが3になってしまい、計算が非効率になってしまいます。木の高さによる更新は以下のようにします。}}木のサイズによる更新は以下のようにします。}}証明は難しいのでこの記事では詳しく説明しませんが、この工夫により計算量が\(O(n)\)から\(O(logn)\)になります。用いて、\(O(\alpha(n))\)で計算できることが知られています(\(O(logn)\)よりも高速)。rankまずはrankによる併合から。