Union-Find

データの集合を素集合（互いにオーバーラップしない集合）に分割して保持する素集合データ構造(disjoint-set data structure)に対して行う、次の操作をUnion-Findアルゴリズムと呼ぶ。

Find: 特定の要素がどの集合(グループ)に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
Union: 2つの集合（グループ）を1つに統合する。

各集合(グループ)は木で表す。なので全体としてはデータ構造は、森(forest)になっている。
グループを表す木は２分木にする必要は無い。基本的に、上に辿る操作のみなので、横に広く低い木の方が高速になる。
Find操作は、指定した要素から親を辿ってルート要素でどの集合（グループ）に属しているかを判断する。
木が偏ると操作が遅くなるので、親を辿るついでに、各要素をルートに直接つなぐ。
Union操作は、一方の集合のルートに他方の集合のルートに繋ぐ。2つの木(集合)を併合するとき、低い木を高い木の根に子として併合すると、併合後の木の高さが押さえられる。なのでルート要素に木の高さを記録しておいて、その情報を見て併合すると良い。

各操作のならし計算量(amortized complexity)は、 $O(\alpha (n))$
$\alpha(n)=A^{-1}(n)$
$A(x) = Ack(x,x)$
$Ack(x,y):$ アッカーマン関数(Ackermann function)
Ackermann function - Wikipedia, the free encyclopediaを見ると、
$A(4) = Ack(4,4) = 2^{2^{2^{65536}}}$ なので、 $\alpha(n)=A^{-1}(n)$ が非常に緩やかな増加だということが分かる。

どいういう時に使えるかを、まとめている方がいたので、リンク張っときます。
自己流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); }
}