素集合データ構造

目的

$n$個の相異なる要素からなる共通部分を持たない集合について、集合の合併と、ある要素同士が同一集合に含まれるかの判定を$O(\alpha(n))$で行います。 ここで、$\alpha$はアッカーマンの逆関数。

計算量

$O(\alpha(n))$

使い方

int n
全要素数
int[] upper
素集合データ構造はデータを根付き木で管理します。upper[x]≥0ならば、xの親はupper[x]です。upper[x]<0ならばxを根とする木の大きさは-upper[x]です。
int root(int u)
uの親をreturnします。uが根である場合はu自身をreturnします。
void setUnion(int u,int v)
uを含む集合とvを含む集合を合併します。
boolean equiv(int u,int v)
u,vが同じ集合に含まれるときtrue、含まれないとき、falseをreturnします。

ソースコード

class DJSet {
	int n;
	int[] upper;

	public DJSet(int n_) {
		n = n_;
		upper = new int[n];
		Arrays.fill(upper, -1);
	}

	boolean equiv(int u, int v) {
		return root(u) == root(v);
	}

	int root(int u) {
		return upper[u] < 0 ? u : (upper[u] = root(upper[u]));
	}

	void setUnion(int u, int v) {
		u = root(u);
		v = root(v);
		if (u == v)
			return;
		if (upper[u] < upper[v]) {
			int d = u;
			u = v;
			v = d;
		}
		upper[v] += upper[u];
		upper[u] = v;
	}
}