完全永続 Union Find
(DataStructure/PersistentUnionFind.hpp)

View this file on GitHub
Last update: 2021-03-18 15:32:11+09:00
Include: #include "DataStructure/PersistentUnionFind.hpp"
Link: https://tkmst201.github.io/Library/DataStructure/PersistentUnionFind.hpp

概要

完全永続になった Union Findです。
過去の任意の状態に対する操作や参照が行えます。

このページでは、完全永続配列 ( $N$ 要素 $M$ 分木) の計算量を次のように仮定しています。

アクセス時間 $\mathcal{O}(M \log_M{N})$ 空間 $\Theta(1)$
更新時間/空間 $\mathcal{O}(M \log_M{N})$

PersistentUnionFind()
- $\Theta(1)$ 初期化
size_t size(size_t x)
- $\mathcal{O}(\frac{(\log{N})^2}{\log{M}})$ 要素 $x$ が属する集合の要素数を返す
size_t find(size_t x)
- $\mathcal{O}(\frac{(\log{N})^2}{\log{M}})$ 要素 $x$ が属する集合の代表元を返します。
PersistentUnionFind unite(size_t x, size_t y)
- 時間 $\mathcal{O}(\frac{(log{N})^2}{\log{M}} + M \frac{log{N}}{\log{M}})$ 空間 $\mathcal{O}(M \frac{\log{N}}{\log{M}})$ 要素 $x$ が属する集合と要素 $y$ が属する集合を併合
void destructive_unite(size_t x, size_t y)
- 時間 $\mathcal{O}(\frac{(log{N})^2}{\log{M}} + M \frac{log{N}}{\log{M}})$ 空間 $\mathcal{O}(M \frac{\log{N}}{\log{M}})$ 要素 $x$ が属する集合と要素 $y$ が属する集合を破壊的に併合
bool issame(size_t x, size_t y)
- $\mathcal{O}(\frac{(\log{N})^2}{\log{M}})$ 要素 $x, y$ が同じ集合に属しているか判定

コンストラクタ

内部を $M$ 分木で管理します。

制約

$M > 1$

PersistentUnionFind()

初期化します。はじめ、すべての要素は自身のみからなる集合に属しています。

計算量

$\Theta(1)$

メンバ関数

以下、アクセスする要素の最大値を $N-1$ とします。

size_t size(size_t x)

要素 $x$ が属する集合の要素数を返します。

制約

$0 \leq x$

計算量

$\mathcal{O}(\frac{(\log{N})^2}{\log{M}})$

size_t find(size_t x)

要素 $x$ が属する集合の代表元を返します。 unite を行うことにより代表元が変化する場合があります。

制約

$0 \leq x$

計算量

$\mathcal{O}(\frac{(\log{N})^2}{\log{M}})$

PersistentUnionFind unite(size_t x, size_t y)

要素 $x$ が属する集合と要素 $y$ が属する集合を併合した Union Find を返します。要素 $x, y$ が同じ集合に属していた場合は自身を返します。

制約

$0 \leq x, y$

計算量

時間 $\mathcal{O}(\frac{(\log{N})^2}{\log{M}} + M \frac{\log{N}}{\log{M}})$
空間 $\mathcal{O}(M \frac{\log{N}}{\log{M}})$

void destructive_unite(size_t x, size_t y)

要素 $x$ が属する集合と要素 $y$ が属する集合を破壊的に併合します。要素 $x, y$ が同じ集合に属していた場合は何も行いません。
この関数を呼んだ後で同一の履歴ツリーに含まれる別の状態にアクセスしたときの動作は未定義です。

制約

$0 \leq x, y$

計算量

時間 $\mathcal{O}(\frac{(\log{N})^2}{\log{M}} + M \frac{\log{N}}{\log{M}})$
空間 $\mathcal{O}(M \frac{\log{N}}{\log{M}})$

bool issame(size_t x, size_t y)

要素 $x, y$ が同じ集合に属しているか判定します。同じ集合に属しているなら $true$ 、違う集合に属しているなら $false$ を返します。

制約

$0 \leq x, y$

計算量

$\mathcal{O}(\frac{(\log{N})^2}{\log{M}})$

使用例

#include <bits/stdc++.h>
#include "DataStructure/PersistentUnionFind.hpp"
using namespace std;

int main() {
	using PUF = PersistentUnionFind<6>;
	
	PUF uf1;
	cout << uf1.find(6) << ", " << uf1.size(6) << endl; // 6, 1
	PUF uf2 = uf1.unite(6, 7);
	cout << uf2.find(6) << ", " << uf2.find(7) << endl; // same (6 or 7)
	cout << uf1.size(6) << ", " << uf2.size(6) << endl; // 1, 2
	
	PUF uf3 = uf2.unite(0, 6);
	cout << uf3.size(0) << endl; // 3
	
	PUF uf4 = uf2.unite(8, 9);
	cout << uf1.size(6) << ", " << uf2.size(6) << ", " << uf4.size(6) << endl; // 1, 2, 2
	uf4.destructive_unite(6, 9);
	// undefined, undefined, 4
	cout << uf1.size(6) << ", " << uf2.size(6) << ", " << uf4.size(6) << endl;
}

解説

経路圧縮は行わずにマージテク (データ構造をマージする一般的なテク) のみ用いています。
マージテクにより 1 クエリあたり高々 $O(log N)$ 個の要素しか関係しません。
実装では、負の数をときは集合の個数を、非負の数のときは親の要素として管理しています。

参考

2020/09/25: https://qiita.com/hotman78/items/9c643feae1de087e6fc5

Depends on

完全永続配列 (DataStructure/PersistentArray.hpp)

Verified with

Test/PersistentUnionFind.test.cpp

Code

#ifndef INCLUDE_GUARD_PERSISTENT_UNION_FIND_HPP
#define INCLUDE_GUARD_PERSISTENT_UNION_FIND_HPP

#include "DataStructure/PersistentArray.hpp"

#include <cstdint>
#include <utility>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentUnionFind.hpp
 */
template<int M>
struct PersistentUnionFind {
	static_assert(M > 1);
	
	using size_type = std::size_t;
	
private:
	using parray_type = PersistentArray<int, M>;
	parray_type dat;
	
public:
	PersistentUnionFind() : dat(-1) {}
	
private:
	PersistentUnionFind(const parray_type & dat) : dat(dat) {}
	
public:
	size_type find(size_type x) const noexcept {
		return find_sub(x).first;
	}
	
	size_type size(size_type x) const noexcept {
		return find_sub(x).second;
	}
	
private:
	std::pair<size_type, int> find_sub(size_type x) const noexcept {
		int d;
		for (d = dat.get(x); d >= 0; d = dat.get(x)) x = d;
		return {x, -d};
	}
	
public:
	PersistentUnionFind unite(size_type x, size_type y) const {
		if (x == y) return *this;
		auto px = find_sub(x), py = find_sub(y);
		if (px.first == py.first) return *this;
		if (px.second > py.second) std::swap(px, py);
		return dat.set(px.first, py.first).set(py.first, -(px.second + py.second));
	}
	
	void destructive_unite(size_type x, size_type y) {
		if (x == y) return;
		auto px = find_sub(x), py = find_sub(y);
		if (px.first == py.first) return;
		if (px.second > py.second) std::swap(px, py);
		dat.destructive_set(px.first, py.first);
		dat.destructive_set(py.first, -(px.second + py.second));
	}
	
	bool issame(size_type x, size_type y) const noexcept {
		return x == y ? true : find(x) == find(y);
	}
};

#endif // INCLUDE_GUARD_PERSISTENT_UNION_FIND_HPP

#line 1 "DataStructure/PersistentUnionFind.hpp"



#line 1 "DataStructure/PersistentArray.hpp"



#include <memory>
#include <utility>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentArray.hpp
 */
template<typename T, int M>
struct PersistentArray {
	static_assert(M > 1);
	
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	
private:
	struct Node;
	using sptr_type = std::shared_ptr<Node>;
	using node_ptr = Node *;
	using const_ptr = const Node *;
	struct Node {
		sptr_type childs[M];
		value_type val;
		Node(const_reference val) : val(val) {}
	};
	
private:
	sptr_type root;
	value_type def_val;
	
private:
	PersistentArray(const sptr_type & root, const_reference def_val) : root(root), def_val(def_val) {}
	
public:
	explicit PersistentArray(const_reference def_val = 0) : root(nullptr), def_val(def_val) {}
	
	PersistentArray set(size_type k, const_reference x) const {
		const_ptr node = root.get();
		sptr_type new_root = std::make_shared<Node>(k == 0 ? x : (node ? node->val : def_val));
		node_ptr new_node = new_root.get();
		for (; k > 0; k /= M) {
			const size_type m = k % M;
			if (node) {
				for (size_type i = 0; i < M; ++i) if (i != m) new_node->childs[i] = node->childs[i];
				new_node->childs[m] = std::make_shared<Node>(k < M ? x : (node->childs[m] ? node->childs[m]->val : def_val));
				node = node->childs[m].get();
			}
			else new_node->childs[m] = std::make_shared<Node>(k < M ? x : def_val);
			new_node = new_node->childs[m].get();
		}
		if (node) for (size_type i = 0; i < M; ++i) new_node->childs[i] = node->childs[i];
		return {std::move(new_root), def_val};
	}
	
	void destructive_set(size_type k, const_reference x) {
		if (!root) root = std::make_shared<Node>(k == 0 ? x : def_val);
		node_ptr node = root.get();
		for (; k >= M; k /= M) {
			const size_type m = k % M;
			if (!node->childs[m]) node->childs[m] = std::make_shared<Node>(def_val);
			node = node->childs[m].get();
		}
		if (node->childs[k]) node->childs[k]->val = x;
		else node->childs[k] = std::make_shared<Node>(x);
	}
	
	const_reference get(size_type k) const noexcept {
		const_ptr node = root.get();
		while (k > 0 && node) {
			node = node->childs[k % M].get();
			k /= M;
		}
		return k == 0 && node ? node->val : def_val;
	}
};


#line 5 "DataStructure/PersistentUnionFind.hpp"

#include <cstdint>
#line 8 "DataStructure/PersistentUnionFind.hpp"

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentUnionFind.hpp
 */
template<int M>
struct PersistentUnionFind {
	static_assert(M > 1);
	
	using size_type = std::size_t;
	
private:
	using parray_type = PersistentArray<int, M>;
	parray_type dat;
	
public:
	PersistentUnionFind() : dat(-1) {}
	
private:
	PersistentUnionFind(const parray_type & dat) : dat(dat) {}
	
public:
	size_type find(size_type x) const noexcept {
		return find_sub(x).first;
	}
	
	size_type size(size_type x) const noexcept {
		return find_sub(x).second;
	}
	
private:
	std::pair<size_type, int> find_sub(size_type x) const noexcept {
		int d;
		for (d = dat.get(x); d >= 0; d = dat.get(x)) x = d;
		return {x, -d};
	}
	
public:
	PersistentUnionFind unite(size_type x, size_type y) const {
		if (x == y) return *this;
		auto px = find_sub(x), py = find_sub(y);
		if (px.first == py.first) return *this;
		if (px.second > py.second) std::swap(px, py);
		return dat.set(px.first, py.first).set(py.first, -(px.second + py.second));
	}
	
	void destructive_unite(size_type x, size_type y) {
		if (x == y) return;
		auto px = find_sub(x), py = find_sub(y);
		if (px.first == py.first) return;
		if (px.second > py.second) std::swap(px, py);
		dat.destructive_set(px.first, py.first);
		dat.destructive_set(py.first, -(px.second + py.second));
	}
	
	bool issame(size_type x, size_type y) const noexcept {
		return x == y ? true : find(x) == find(y);
	}
};

完全永続 Union Find (DataStructure/PersistentUnionFind.hpp)

概要

コンストラクタ

PersistentUnionFind()

メンバ関数

size_t size(size_t x)

size_t find(size_t x)

PersistentUnionFind unite(size_t x, size_t y)

void destructive_unite(size_t x, size_t y)

bool issame(size_t x, size_t y)

使用例

解説

参考

Depends on

Verified with

Code

完全永続 Union Find
(DataStructure/PersistentUnionFind.hpp)