This documentation is automatically generated by online-judge-tools/verification-helper
#include "library/datastructure/union_find/linked_union_find.hpp"
名前が分かりません。素集合の要素の列挙と併合 (単方向循環リスト) これです。
頂点 $v$ が属する連結成分 $C$ を $O(\vert C\vert)$ で取得可能である。
#ifndef SUISEN_LINKED_UNION_FIND
#define SUISEN_LINKED_UNION_FIND
#include <numeric>
#include "library/datastructure/union_find/union_find.hpp"
namespace suisen {
struct LinkedUnionFind : public UnionFind {
LinkedUnionFind() = default;
explicit LinkedUnionFind(int n) : UnionFind(n), _link(n) {
std::iota(_link.begin(), _link.end(), 0);
}
// Merge two vertices `x` and `y`.
bool merge(int x, int y) {
if (UnionFind::merge(x, y)) {
std::swap(_link[x], _link[y]);
return true;
}
return false;
}
// Get items connected to `x` (including `x`). Let the size of return value be `m`, time complexity is O(m).
std::vector<int> connected_component(int x) const {
std::vector<int> comp{ x };
for (int y = _link[x]; y != x; y = _link[y]) comp.push_back(y);
return comp;
}
protected:
std::vector<int> _link;
};
} // namespace suisen
#endif // SUISEN_LINKED_UNION_FIND
#line 1 "library/datastructure/union_find/linked_union_find.hpp"
#include <numeric>
#line 1 "library/datastructure/union_find/union_find.hpp"
#include <algorithm>
#include <vector>
namespace suisen {
struct UnionFind {
UnionFind() = default;
explicit UnionFind(int _n) : _n(_n), _dat(_n, -1) {}
// Get the root of `x`. equivalent to `operator[](x)`
int root(int x) {
static std::vector<int> buf;
while (_dat[x] >= 0) buf.push_back(x), x = _dat[x];
while (buf.size()) _dat[buf.back()] = x, buf.pop_back();
return x;
}
// Get the root of `x`. euivalent to `root(x)`
int operator[](int x) {
return root(x);
}
// Merge two vertices `x` and `y`.
bool merge(int x, int y) {
x = root(x), y = root(y);
if (x == y) return false;
if (_dat[x] > _dat[y]) std::swap(x, y);
_dat[x] += _dat[y], _dat[y] = x;
return true;
}
// Check if `x` and `y` belongs to the same connected component.
bool same(int x, int y) {
return root(x) == root(y);
}
// Get the size of connected componet to which `x` belongs.
int size(int x) {
return -_dat[root(x)];
}
// Get all of connected components.
std::vector<std::vector<int>> groups() {
std::vector<std::vector<int>> res(_n);
for (int i = 0; i < _n; ++i) res[root(i)].push_back(i);
res.erase(std::remove_if(res.begin(), res.end(), [](const auto& g) { return g.empty(); }), res.end());
return res;
}
protected:
int _n;
std::vector<int> _dat;
};
} // namespace suisen
#line 6 "library/datastructure/union_find/linked_union_find.hpp"
namespace suisen {
struct LinkedUnionFind : public UnionFind {
LinkedUnionFind() = default;
explicit LinkedUnionFind(int n) : UnionFind(n), _link(n) {
std::iota(_link.begin(), _link.end(), 0);
}
// Merge two vertices `x` and `y`.
bool merge(int x, int y) {
if (UnionFind::merge(x, y)) {
std::swap(_link[x], _link[y]);
return true;
}
return false;
}
// Get items connected to `x` (including `x`). Let the size of return value be `m`, time complexity is O(m).
std::vector<int> connected_component(int x) const {
std::vector<int> comp{ x };
for (int y = _link[x]; y != x; y = _link[y]) comp.push_back(y);
return comp;
}
protected:
std::vector<int> _link;
};
} // namespace suisen