This documentation is automatically generated by online-judge-tools/verification-helper
#include "DataStructure/PotentializedUnionFind.hpp"
差分制約の一次方程式を効率的に解くことができるデータ構造です。
変数が $N$ 個あるとき、差分制約の追加や差分の計算をならし $\Theta(\alpha(N))$ ( $\alpha(N)$ はアッカーマン関数の逆関数 ) で計算できます。
Union Find の機能強化版です。
PotentializedUnionFind(size_t n, const T & id_elem, const F & f, const F & g = [];(const_refrence x) { return -x; })
:warning: size_t size(size_t x)
size_t find(size_t x)
void merge(size_t x, size_t y, const T & w)
T diff(size_t x, size_t y)
bool issame(size_t x, size_t y)
$n$ 変数で初期化します。 はじめ、すべての変数は自身のみからなるグループに属しています。
制約
f
の単位元は id_elem
g
は逆元を返すid_elem
, g
$)$ はアーベル群計算量
以下、変数の個数を $N$ とします。 また、アッカーマン関数の逆関数を $\alpha(N)$ と表します。
変数 $x$ と同じグループに含まれる変数の個数を返します。
制約
計算量
変数 $x$ が属するグループの代表の変数を返します。
unite
を行うことにより代表の変数が変化する場合があります。
制約
計算量
変数 $x, y$ それぞれが属するグループを併合し、差分制約 $x + w = y$ を追加します。
制約
計算量
これまでに追加された差分制約を満たすような変数 $x, y$ の値に対して $y - x$ を返します。
制約
計算量
変数 $x, y$ が同じグループに属しているか判定します。 同じグループに属しているなら $true$ 、違うグループに属しているなら $false$ を返します。
制約
計算量
#include <bits/stdc++.h>
#include "DataStructure/PotentializedUnionFind.hpp"
using namespace std;
int main() {
PotentializedUnionFind<int> puf(3, 0, [](auto x, auto y) { return x + y; });
puf.merge(1, 0, 5); // x0 - x1 = 5
cout << "diff(1, 0) = " << puf.diff(1, 0) << endl; // 5
puf.merge(1, 2, 7); // x2 - x1 = 7
cout << "diff(2, 1) = " << puf.diff(2, 1) << endl; // -7
// => x0 - x2 = -2
cout << "diff(2, 0) = " << puf.diff(2, 0) << endl;
// => x0 - x2 = 2
cout << "diff(0, 2) = " << puf.diff(0, 2) << endl;
PotentializedUnionFind<int> pufxor(5, 0, [](auto x, auto y) { return x ^ y; }, [](auto x) { return x; });
pufxor.merge(1, 0, 1); // x1 ^ x0 = 1
pufxor.merge(1, 2, 2); // x2 ^ x1 = 2
// => x2 ^ x0 = 3
cout << "diff(2, 0) = " << pufxor.diff(2, 0) << endl;
// => x0 ^ x2 = 3
cout << "diff(0, 2) = " << pufxor.diff(2, 0) << endl;
for (int i = 0; i < 5; ++i) cout << pufxor.size(i) << " \n"[i + 1 == 5]; // 3 3 3 1 1
cout << "issame(0, 1) = " << boolalpha << pufxor.issame(0, 1) << endl; // true
cout << "issame(2, 3) = " << boolalpha << pufxor.issame(2, 3) << endl; // false
cout << "find(2) = " << pufxor.find(2) << endl; // 0 or 1 or 2
cout << "find(4) = " << pufxor.find(4) << endl; // 4
}
TODO: size
の test を追加する
2021/03/09: http://sigma425.hatenablog.com/entry/2015/12/07/185047
2021/03/09: https://qiita.com/drken/items/cce6fc5c579051e64fab
#ifndef INCLUDE_GUARD_POTENTIALIZED_UNION_FIND_HPP
#define INCLUDE_GUARD_POTENTIALIZED_UNION_FIND_HPP
#include <cassert>
#include <vector>
#include <functional>
#include <utility>
/**
* @brief https://tkmst201.github.io/Library/DataStructure/PotentializedUnionFind.hpp
*/
template<typename T>
struct PotentializedUnionFind {
using value_type = T;
using const_reference = const value_type &;
using size_type = std::size_t;
using F = std::function<value_type (const_reference, const_reference)>;
using G = std::function<value_type (const_reference)>;
private:
size_type n;
value_type id_elem;
F f;
G g;
std::vector<int> dat;
std::vector<value_type> val;
public:
PotentializedUnionFind(size_type n, const_reference id_elem, const F & f, const G & g = [](const_reference x) { return -x; })
: n(n), id_elem(id_elem), f(f), g(g), dat(n, -1), val(n, id_elem) {}
size_type size(size_type x) noexcept {
assert(x < n);
return -dat[find(x)];
}
size_type find(size_type x) noexcept {
assert(x < n);
if (dat[x] < 0) return x;
const size_type p = dat[x];
dat[x] = find(p);
val[x] = f(val[x], val[p]);
return dat[x];
}
void merge(size_type x, size_type y, const_reference w) noexcept {
assert(x < n);
assert(y < n);
size_type rx = find(x), ry = find(y);
assert(rx != ry);
value_type v = f(val[y], g(f(val[x], w)));
if (dat[rx] < dat[ry]) {
std::swap(rx, ry);
v = g(v);
}
dat[ry] += dat[rx];
dat[rx] = ry;
val[rx] = std::move(v);
}
value_type diff(size_type x, size_type y) noexcept {
assert(x < n);
assert(y < n);
const size_type rx = find(x), ry = find(y);
assert(rx == ry);
return f(val[y], g(val[x]));
}
bool issame(size_type x, size_type y) noexcept {
assert(x < n);
assert(y < n);
return find(x) == find(y);
}
};
#endif // INCLUDE_GUARD_POTENTIALIZED_UNION_FIND_HPP
#line 1 "DataStructure/PotentializedUnionFind.hpp"
#include <cassert>
#include <vector>
#include <functional>
#include <utility>
/**
* @brief https://tkmst201.github.io/Library/DataStructure/PotentializedUnionFind.hpp
*/
template<typename T>
struct PotentializedUnionFind {
using value_type = T;
using const_reference = const value_type &;
using size_type = std::size_t;
using F = std::function<value_type (const_reference, const_reference)>;
using G = std::function<value_type (const_reference)>;
private:
size_type n;
value_type id_elem;
F f;
G g;
std::vector<int> dat;
std::vector<value_type> val;
public:
PotentializedUnionFind(size_type n, const_reference id_elem, const F & f, const G & g = [](const_reference x) { return -x; })
: n(n), id_elem(id_elem), f(f), g(g), dat(n, -1), val(n, id_elem) {}
size_type size(size_type x) noexcept {
assert(x < n);
return -dat[find(x)];
}
size_type find(size_type x) noexcept {
assert(x < n);
if (dat[x] < 0) return x;
const size_type p = dat[x];
dat[x] = find(p);
val[x] = f(val[x], val[p]);
return dat[x];
}
void merge(size_type x, size_type y, const_reference w) noexcept {
assert(x < n);
assert(y < n);
size_type rx = find(x), ry = find(y);
assert(rx != ry);
value_type v = f(val[y], g(f(val[x], w)));
if (dat[rx] < dat[ry]) {
std::swap(rx, ry);
v = g(v);
}
dat[ry] += dat[rx];
dat[rx] = ry;
val[rx] = std::move(v);
}
value_type diff(size_type x, size_type y) noexcept {
assert(x < n);
assert(y < n);
const size_type rx = find(x), ry = find(y);
assert(rx == ry);
return f(val[y], g(val[x]));
}
bool issame(size_type x, size_type y) noexcept {
assert(x < n);
assert(y < n);
return find(x) == find(y);
}
};