Union-Find木の使い方

Union-Find木の書き方、使い方をまとめた

Union-Find木は、以下のことができるデータ構造である。

1, 要素aと要素bのグループを併合する。
2, 要素aと要素bが同じグループに入っているか判定する。

(1)書き方

main関数の上に次のように書く

class UnionFindTree {
private:
	std::vector<int> par;   // 親
	std::vector<int> depth; // 木の深さ

public:
	// n要素で初期化
	UnionFindTree(int n) {
		for (int i = 0; i < n; i++) {
			par.push_back(i);
			depth.push_back(0);
		}
	}

	// 木の根を求める
	int find(int x) {
		if (par[x] == x) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}

	// xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)
			return;

		if (depth[x] < depth[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (depth[x] == depth[y])
				depth[x]++;
		}
	}

	// xとyが同じ集合に属するか否か
	bool same(int x, int y) { return find(x) == find(y); }
};

(2)使い方

[例]次の図のような構造を考える。

図1 : Union-Find木で表現するデータ

この集合は、次のように3つのグループに分けることができる。

(0,1,2,3)
(4,5,6)
(7)

※同じグループ同士は辺を通って行き来できるというイメージ。

Union-Find木で図1のデータを表現する。

(1)宣言

Union-Find木を宣言する。
「UnionFindTree 名前 = UnionFindTree(要素数);」
で宣言できる。

int N = 8;//要素数
UnionFindTree UFT = UnionFindTree(N);

これでUFTという名前のUnion-Find木を要素数8で宣言できた。

(2)要素同士の結合

図1で繋がっている辺を見て要素同士を結合していく。
「名前.unite(a, b);」で要素aと要素bを結合できる。

UFT.unite(1, 0);
UFT.unite(1, 2);
UFT.unite(1, 3);
UFT.unite(4, 5);
UFT.unite(4, 6);
UFT.unite(5, 6);

これで要素同士をつなぐことができたので図1のデータがUnion-Find木で表現できた。

(3)同じグループであるか判定

「名前.same(a, b)」でaとbが同じグループであるか判定できる。（同じグループならtrue,違うグループならfalseを返す。）

cout << UFT.same(1, 2) << endl;
cout << UFT.same(0, 3) << endl;
cout << UFT.same(2, 4) << endl;

これの出力結果は

1
1
0

である。

1と2は同じグループ
0と3は同じグループ
2と4は違うグループ

ということだ。確かに正しい。

Union-Find木の結合、判定の計算量は要素数をNとすると、O(α(N)) である。
α(N)は、Nのアッカーマン関数の逆関数といい、log(N)よりも小さい。