Union-Find
Union-Find
データの集合を素集合(互いにオーバーラップしない集合)に分割して保持する素集合データ構造(disjoint-set data structure)に対して行う、次の操作をUnion-Findアルゴリズムと呼ぶ。
- Find: 特定の要素がどの集合(グループ)に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
- Union: 2つの集合(グループ)を1つに統合する。
各集合(グループ)は木で表す。なので全体としてはデータ構造は、森(forest)になっている。
グループを表す木は2分木にする必要は無い。基本的に、上に辿る操作のみなので、横に広く低い木の方が高速になる。
Find操作は、指定した要素から親を辿ってルート要素でどの集合(グループ)に属しているかを判断する。
木が偏ると操作が遅くなるので、親を辿るついでに、各要素をルートに直接つなぐ。
Union操作は、一方の集合のルートに他方の集合のルートに繋ぐ。2つの木(集合)を併合するとき、低い木を高い木の根に子として併合すると、併合後の木の高さが押さえられる。なのでルート要素に木の高さを記録しておいて、その情報を見て併合すると良い。
各操作のならし計算量(amortized complexity)は、
アッカーマン関数(Ackermann function)
Ackermann function - Wikipedia, the free encyclopediaを見ると、
なので、が非常に緩やかな増加だということが分かる。
どいういう時に使えるかを、まとめている方がいたので、リンク張っときます。
自己流union-findの使い方 - DEGwerの競技プログラミングと時々数学。
コード
要素数をnを与えて、{{0},{1},...,{n-1}}で初期化する。
parent[x]配列はある要素xの親要素を示すが、負の数になっている場合、xはルートで、-parent[x]は木(グループ)の要素数を示す。
numは木(グループ)の数で、初期化時は、nで、併合するときにデクリメントすればいい。
//※swap(int[] x, int i, int j){ int tmp = x[i]; x[i] = x[j]; x[j] = tmp; } public class UnionFind { private int num; // number of disjoint sets (group) private final int[] parent; //parent[x] = parent of x //※ case parent[x] < 0: x = root, -parent[x] = size of set containing x /** * Initialization with {{0},{1},...,{size-1}} * @param size */ public UnionFind(int size) { parent = new int[size]; num = size; Arrays.fill(parent, -1); } /** * Gets root of x.<br> * n = number of elements, A(a) = Ackermann function(a,a), amortized complexity O(A^-1(n)). * @param x * @return Root of x. */ public final int root(int x) { return parent[x] < 0 ? x : (parent[x] = root(parent[x])); } /** * Gets number of disjoint sets (group). O(1) * @return Number of disjoint sets. */ public final int size() { return num; } /** * Gets size of set containing x.<br> * n = number of elements, A(a) = Ackermann function(a,a), amortized complexity O(A^-1(n)). * @param x * @return Size of set containing x. */ public final int size(int x) { return -parent[root(x)]; } /** * Merges S(x) with S(y). ※S(e) is set containing e.<br> * n = number of elements, A(a) = Ackermann function(a,a), amortized complexity O(A^-1(n)). * @param x * @param y * @return true -> Success merge, false -> Already merged */ public final boolean union(int x, int y) { x = root(x); y = root(y); if (x != y) { if (parent[y] < parent[x]) swap(parent, x, y); parent[x] += parent[y]; //sets size of set containing x. parent[y] = x; //sets parent of y. --num; } return x != y; } /** * Tests whether S(x) == S(y) or not. ※S(e) is set containing e.<br> * n = number of elements, A(a) = Ackermann function(a,a), amortized complexity O(A^-1(n)). * @param x * @param y * @return Whether S(x) == S(y) or not. */ public final boolean find(int x, int y) { return root(x) == root(y); } }