C++ Library for Competitive Programming
#include "emthrm/data_structure/union-find/weighted_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_WEIGHTED_UNION_FIND_HPP_
#define EMTHRM_DATA_STRUCTURE_UNION_FIND_WEIGHTED_UNION_FIND_HPP_
#include <utility>
#include <vector>
namespace emthrm {
template <typename Abelian>
struct WeightedUnionFind {
explicit WeightedUnionFind(const int n, const Abelian ID = 0)
: ID(ID), parent(n, -1), data(n, ID) {}
int root(const int ver) {
if (parent[ver] < 0) return ver;
const int r = root(parent[ver]);
data[ver] += data[parent[ver]];
return parent[ver] = r;
}
bool unite(int u, int v, Abelian wt) {
wt += weight(u);
wt -= weight(v);
u = root(u);
v = root(v);
if (u == v) return false;
if (parent[u] > parent[v]) {
std::swap(u, v);
wt = -wt;
}
parent[u] += parent[v];
parent[v] = u;
data[v] = wt;
return true;
}
bool is_same(const int u, const int v) { return root(u) == root(v); }
int size(const int ver) { return -parent[root(ver)]; }
Abelian diff(const int u, const int v) { return weight(v) - weight(u); }
private:
const Abelian ID;
std::vector<int> parent;
std::vector<Abelian> data;
Abelian weight(const int ver) {
root(ver);
return data[ver];
}
};
} // namespace emthrm
#endif // EMTHRM_DATA_STRUCTURE_UNION_FIND_WEIGHTED_UNION_FIND_HPP_
#line 1 "include/emthrm/data_structure/union-find/weighted_union-find.hpp"
#include <utility>
#include <vector>
namespace emthrm {
template <typename Abelian>
struct WeightedUnionFind {
explicit WeightedUnionFind(const int n, const Abelian ID = 0)
: ID(ID), parent(n, -1), data(n, ID) {}
int root(const int ver) {
if (parent[ver] < 0) return ver;
const int r = root(parent[ver]);
data[ver] += data[parent[ver]];
return parent[ver] = r;
}
bool unite(int u, int v, Abelian wt) {
wt += weight(u);
wt -= weight(v);
u = root(u);
v = root(v);
if (u == v) return false;
if (parent[u] > parent[v]) {
std::swap(u, v);
wt = -wt;
}
parent[u] += parent[v];
parent[v] = u;
data[v] = wt;
return true;
}
bool is_same(const int u, const int v) { return root(u) == root(v); }
int size(const int ver) { return -parent[root(ver)]; }
Abelian diff(const int u, const int v) { return weight(v) - weight(u); }
private:
const Abelian ID;
std::vector<int> parent;
std::vector<Abelian> data;
Abelian weight(const int ver) {
root(ver);
return data[ver];
}
};
} // namespace emthrm