重み付き Union-Find

data_structure/weighted_union_find.hpp · GitHub で見る

共通ページ

#include "lib/data_structure/weighted_union_find.hpp"

WeightedUnionFind<std::int64_t> uf(3);
bool ok = uf.merge(0, 1, 5); // true
auto value = uf.diff(0, 1); // 5

操作	内容・返り値	計算量
WeightedUnionFind<T>(n)	n 頂点を独立した成分として構築	\(O(n)\)
merge(x,y,w)	\(\mathrm{potential}[y]-\mathrm{potential}[x]=w\) を追加。矛盾時に false	償却 \(O(\alpha(n))\)
same(x,y)	連結判定	償却 \(O(\alpha(n))\)
leader(x) / size(x)	代表元／連結成分の頂点数	償却 \(O(\alpha(n))\)
weight(x)	代表元を基準とする x のポテンシャル	償却 \(O(\alpha(n))\)
diff(x,y)	連結な頂点間の \(\mathrm{potential}[y]-\mathrm{potential}[x]\)	償却 \(O(\alpha(n))\)

merge(x, y, w) は \(\mathrm{potential}[y]-\mathrm{potential}[x]=w\) を追加し、矛盾する場合に false を返します。diff(x, y) は連結な頂点間の \(\mathrm{potential}[y]-\mathrm{potential}[x]\) を返します。

same(x, y) で連結判定、leader(x) で代表元、size(x) で連結成分の頂点数を取得できます。頂点番号は 0 始まりです。

例では頂点 1 の値が頂点 0 より 5 大きいという関係を登録しています。絶対的な値を指定する必要はありません。diff の前に same で連結を確認してください。既存の関係と矛盾する merge は false を返し、関係を変更しません。

頂点数を \(n\) として、構築・空間は \(O(n)\)、各操作は償却 \(O(\alpha(n))\) です。\(\alpha\) は逆アッカーマン関数で、T の演算・コピーは \(O(1)\) とします。

検証コード

• test/weighted_union_find.test.cpp

コード

#ifndef WEIGHTED_UNION_FIND_HPP
#define WEIGHTED_UNION_FIND_HPP

#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

template <class T = std::int64_t>
struct WeightedUnionFind {
	std::vector<int> parent;
	std::vector<T> delta;
	explicit WeightedUnionFind(int n) {
		assert(n >= 0);
		parent.assign(n, -1);
		delta.resize(n);
	}
	int leader(int x) {
		assert(0 <= x && x < static_cast<int>(parent.size()));
		int p = parent[x];
		if (p < 0) return x;
		if (parent[p] < 0) return p;
		int r = leader(p);
		delta[x] += delta[parent[x]];
		return parent[x] = r;
	}
	T weight(int x) {
		leader(x);
		return delta[x];
	}
	bool same(int x, int y) { return leader(x) == leader(y); }
	int size(int x) { return -parent[leader(x)]; }
	T diff(int x, int y) {
		[[maybe_unused]] int rx = leader(x), ry = leader(y);
		assert(rx == ry);
		return delta[y] - delta[x];
	}
	bool merge(int x, int y, T w) {
		int rx = leader(x), ry = leader(y);
		w += delta[x] - delta[y];
		if (rx == ry) return w == T(0);
		if (parent[rx] > parent[ry]) std::swap(rx, ry), w = -w;
		parent[rx] += parent[ry];
		parent[ry] = rx;
		delta[ry] = w;
		return true;
	}
};

#endif

Back to top page