C++ Library for Competitive Programming
#include "emthrm/data_structure/union-find/undoable_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_UNDOABLE_UNION_FIND_HPP_
#define EMTHRM_DATA_STRUCTURE_UNION_FIND_UNDOABLE_UNION_FIND_HPP_
#include <utility>
#include <vector>
namespace emthrm {
struct UndoableUnionFind {
explicit UndoableUnionFind(const int n) : data(n, -1) {}
int root(const int ver) const {
return data[ver] < 0 ? ver : root(data[ver]);
}
bool unite(int u, int v) {
u = root(u);
history.emplace_back(u, data[u]);
v = root(v);
history.emplace_back(v, data[v]);
if (u == v) return false;
if (data[u] > data[v]) std::swap(u, v);
data[u] += data[v];
data[v] = u;
return true;
}
bool is_same(const int u, const int v) const { return root(u) == root(v); }
int size(const int ver) const { return -data[root(ver)]; }
void undo() {
for (int i = 0; i < 2; ++i) {
data[history.back().first] = history.back().second;
history.pop_back();
}
}
void snapshot() { history.clear(); }
void rollback() {
while (!history.empty()) undo();
}
private:
std::vector<int> data;
std::vector<std::pair<int, int>> history;
};
} // namespace emthrm
#endif // EMTHRM_DATA_STRUCTURE_UNION_FIND_UNDOABLE_UNION_FIND_HPP_
#line 1 "include/emthrm/data_structure/union-find/undoable_union-find.hpp"
#include <utility>
#include <vector>
namespace emthrm {
struct UndoableUnionFind {
explicit UndoableUnionFind(const int n) : data(n, -1) {}
int root(const int ver) const {
return data[ver] < 0 ? ver : root(data[ver]);
}
bool unite(int u, int v) {
u = root(u);
history.emplace_back(u, data[u]);
v = root(v);
history.emplace_back(v, data[v]);
if (u == v) return false;
if (data[u] > data[v]) std::swap(u, v);
data[u] += data[v];
data[v] = u;
return true;
}
bool is_same(const int u, const int v) const { return root(u) == root(v); }
int size(const int ver) const { return -data[root(ver)]; }
void undo() {
for (int i = 0; i < 2; ++i) {
data[history.back().first] = history.back().second;
history.pop_back();
}
}
void snapshot() { history.clear(); }
void rollback() {
while (!history.empty()) undo();
}
private:
std::vector<int> data;
std::vector<std::pair<int, int>> history;
};
} // namespace emthrm