C++ Library for Competitive Programming
#include "emthrm/data_structure/union-find/partially_persistent_union-find.hpp"
名前 | 概要 |
---|---|
union-find | 互いに素な集合族を管理するデータ構造 |
重みつき union-find | アーベル群上の重みを考慮した union-find |
部分永続 union-find | ある時刻における状態を保存する union-find である。最新版のみ変更できる。 |
undo 可能 union-find | 巻き戻し可能な union-find |
時間計算量 | |
---|---|
union-find | $\langle O(N), \text{amortized } O(\alpha(N)) \rangle$ |
重みつき union-find | $\langle O(N), \text{amortized } O(\alpha(N)) \rangle$ |
部分永続 union-find | $\langle O(N), O(\log{N}) \rangle$ |
undo 可能 union-find | $\langle O(N), O(\log{N}) \rangle$ |
struct UnionFind;
名前 | 効果・戻り値 |
---|---|
explicit UnionFind(const int n); |
頂点数 $N$ のオブジェクトを構築する。 |
int root(const int ver); |
$\mathrm{ver}$ の根 |
bool unite(int u, int v); |
$u$ と $v$ を併合したのち、操作前は $u$ と $v$ が異なる集合に属していたかを返す。 |
bool is_same(const int u, const int v); |
$u$ と $v$ は同じ集合に属しているか。 |
int size(const int ver); |
$\mathrm{ver}$ を含む集合のサイズ |
template <typename Abelian>
struct WeightedUnionFind;
Abelian
:アーベル群である要素型名前 | 効果・戻り値 |
---|---|
explicit WeightedUnionFind(const int n, const Abelian ID = 0); |
頂点数 $N$、単位元 $\mathrm{id}$ のオブジェクトを構築する。 |
int root(const int ver); |
$\mathrm{ver}$ の根 |
bool unite(int u, int v, Abelian wt); |
$w(u) + \mathrm{wt} = w(v)$ の情報を加えたのち、操作前は $u$ と $v$ が異なる集合に属していたかを返す。 |
bool is_same(const int u, const int v); |
$u$ と $v$ は同じ集合に属しているか。 |
int size(const int ver); |
$\mathrm{ver}$ を含む集合のサイズ |
Abelian diff(const int u, const int v); |
$w(v) - w(u)$ |
struct PartiallyPersistentUnionFind;
名前 | 効果・戻り値 |
---|---|
explicit PartiallyPersistentUnionFind(const int n); |
頂点数 $N$ のオブジェクトを構築する。 |
int root(const int t, const int ver) const; |
時刻 $t$ における $\mathrm{ver}$ の根 |
bool unite(const int t, int u, int v); |
時刻 $t$ に $u$ と $v$ を併合したのち、操作前は $u$ と $v$ が異なる集合に属していたかを返す。 |
bool is_same(const int t, const int u, const int v) const; |
時刻 $t$ に $u$ と $v$ は同じ集合に属しているか。 |
int size(const int t, int ver) const; |
時刻 $t$ における $\mathrm{ver}$ を含む集合のサイズ |
struct UndoableUnionFind;
名前 | 効果・戻り値 |
---|---|
explicit UndoableUnionFind(const int n); |
頂点数 $N$ のオブジェクトを構築する。 |
int root(const int ver) const; |
$\mathrm{ver}$ の根 |
bool unite(int u, int v); |
$u$ と $v$ を併合したのち、操作前は $u$ と $v$ が異なる集合に属していたかを返す。 |
bool is_same(const int u, const int v) const; |
$u$ と $v$ は同じ集合に属しているか。 |
int size(const int ver) const; |
$\mathrm{ver}$ を含む集合のサイズ |
void undo(); |
unite を一度だけ巻き戻す。 |
void snapshot(); |
スナップショット |
void rollback(); |
snapshot 時点まで巻き戻す。 |
union-find
重みつき union-find
部分永続 union-find
undo 可能 union-find
#ifndef EMTHRM_DATA_STRUCTURE_UNION_FIND_PARTIALLY_PERSISTENT_UNION_FIND_HPP_
#define EMTHRM_DATA_STRUCTURE_UNION_FIND_PARTIALLY_PERSISTENT_UNION_FIND_HPP_
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>
namespace emthrm {
struct PartiallyPersistentUnionFind {
explicit PartiallyPersistentUnionFind(const int n)
: data(n, -1), last(n, -1), history(n, {{-1, -1}}) {}
int root(const int t, const int ver) const {
return last[ver] == -1 || t < last[ver] ? ver : root(t, data[ver]);
}
bool unite(const int t, int u, int v) {
u = root(t, u);
v = root(t, v);
if (u == v) return false;
if (data[u] > data[v]) std::swap(u, v);
data[u] += data[v];
data[v] = u;
last[v] = t;
history[u].emplace_back(t, data[u]);
return true;
}
bool is_same(const int t, const int u, const int v) const {
return root(t, u) == root(t, v);
}
int size(const int t, int ver) const {
ver = root(t, ver);
return -std::prev(std::lower_bound(history[ver].begin(),
history[ver].end(),
std::make_pair(t, 0)))->second;
}
private:
std::vector<int> data, last;
std::vector<std::vector<std::pair<int, int>>> history;
};
} // namespace emthrm
#endif // EMTHRM_DATA_STRUCTURE_UNION_FIND_PARTIALLY_PERSISTENT_UNION_FIND_HPP_
#line 1 "include/emthrm/data_structure/union-find/partially_persistent_union-find.hpp"
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>
namespace emthrm {
struct PartiallyPersistentUnionFind {
explicit PartiallyPersistentUnionFind(const int n)
: data(n, -1), last(n, -1), history(n, {{-1, -1}}) {}
int root(const int t, const int ver) const {
return last[ver] == -1 || t < last[ver] ? ver : root(t, data[ver]);
}
bool unite(const int t, int u, int v) {
u = root(t, u);
v = root(t, v);
if (u == v) return false;
if (data[u] > data[v]) std::swap(u, v);
data[u] += data[v];
data[v] = u;
last[v] = t;
history[u].emplace_back(t, data[u]);
return true;
}
bool is_same(const int t, const int u, const int v) const {
return root(t, u) == root(t, v);
}
int size(const int t, int ver) const {
ver = root(t, ver);
return -std::prev(std::lower_bound(history[ver].begin(),
history[ver].end(),
std::make_pair(t, 0)))->second;
}
private:
std::vector<int> data, last;
std::vector<std::vector<std::pair<int, int>>> history;
};
} // namespace emthrm