This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/datastructure/union_find/persistent_union_find.hpp"
#ifndef SUISEN_PERSISTENT_UNION_FIND #define SUISEN_PERSISTENT_UNION_FIND #include <algorithm> #include <utility> #include "library/datastructure/persistent_array.hpp" namespace suisen { struct PersistentUnionFind { using array_type = PersistentArray<int, 4>; PersistentUnionFind() = default; explicit PersistentUnionFind(int n) : _n(n), _dat(_n, -1) {} static void init_pool(int capacity) { array_type::init_pool(capacity); } // Get the root of `x`. equivalent to `operator[](x)` int root(int x) { static std::vector<int> buf; while (true) { if (int r = _dat.get(x); r >= 0) buf.push_back(std::exchange(x, r)); else break; } while (buf.size()) _dat.mut_set(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`. std::pair<PersistentUnionFind, bool> merge(int x, int y) { x = root(x), y = root(y); if (x == y) return { *this, false }; int vx = _dat.get(x), vy = _dat.get(y); if (vx > vy) std::swap(x, y), std::swap(vx, vy); array_type new_dat = _dat; new_dat = new_dat.set(x, vx + vy); new_dat = new_dat.set(y, x); return { PersistentUnionFind(new_dat), 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.get(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; } std::vector<int> dump() { return _dat.dump(); } protected: int _n; array_type _dat; explicit PersistentUnionFind(array_type dat) : _n(dat.size()), _dat(dat) {} }; } // namespace suisen #endif // SUISEN_PERSISTENT_UNION_FIND
#line 1 "library/datastructure/union_find/persistent_union_find.hpp" #include <algorithm> #include <utility> #line 1 "library/datastructure/persistent_array.hpp" #line 1 "library/util/object_pool.hpp" #include <deque> #include <vector> namespace suisen { template <typename T, bool auto_extend = false> struct ObjectPool { using value_type = T; using value_pointer_type = T*; template <typename U> using container_type = std::conditional_t<auto_extend, std::deque<U>, std::vector<U>>; container_type<value_type> pool; container_type<value_pointer_type> stock; decltype(stock.begin()) it; ObjectPool() : ObjectPool(0) {} ObjectPool(int siz) : pool(siz), stock(siz) { clear(); } int capacity() const { return pool.size(); } int size() const { return it - stock.begin(); } value_pointer_type alloc() { if constexpr (auto_extend) ensure(); return *it++; } void free(value_pointer_type t) { *--it = t; } void clear() { int siz = pool.size(); it = stock.begin(); for (int i = 0; i < siz; i++) stock[i] = &pool[i]; } void ensure() { if (it != stock.end()) return; int siz = stock.size(); for (int i = siz; i <= siz * 2; ++i) { stock.push_back(&pool.emplace_back()); } it = stock.begin() + siz; } }; } // namespace suisen #line 6 "library/datastructure/persistent_array.hpp" namespace suisen { template <typename T, int lg_ary = 4> struct PersistentArray { struct Node; using node_type = Node; using node_pointer_type = node_type*; using value_type = T; using pool_type = ObjectPool<node_type>; struct Node { static inline pool_type pool{}; static constexpr int mask = (1 << lg_ary) - 1; node_pointer_type _ch[1 << lg_ary]{}; value_type _val; Node(const value_type& val = value_type{}) : _val(val) {} static node_pointer_type clone(node_pointer_type node) { return &(*pool.alloc() = *node); } static node_pointer_type new_node(const value_type& val) { return &(*pool.alloc() = node_type(val)); } static value_type& get(node_pointer_type node, int id) { for (; id; --id >>= lg_ary) node = node->_ch[id & mask]; return node->_val; } static node_pointer_type set(node_pointer_type node, int id, const value_type& val) { node_pointer_type res = clone(node), cur = res; for (; id; --id >>= lg_ary) cur = cur->_ch[id & mask] = clone(cur->_ch[id & mask]); cur->_val = val; return res; } static value_type mut_set(node_pointer_type node, int id, const value_type& val) { return std::exchange(get(node, id), val); } static node_pointer_type build(const std::vector<value_type>& init) { const int n = init.size(); if (n == 0) return nullptr; auto dfs = [&](auto dfs, node_pointer_type cur, int id, int p) -> void { int np = p << lg_ary, nid = id + p; for (int d = 1; d < 1 << lg_ary; ++d, nid += p) { if (nid < n) dfs(dfs, cur->_ch[d] = new_node(init[nid]), nid, np); else return; } if (nid < n) dfs(dfs, cur->_ch[0] = new_node(init[nid]), nid, np); }; node_pointer_type root = new_node(init[0]); dfs(dfs, root, 0, 1); return root; } static std::vector<value_type> dump(node_pointer_type node) { if (not node) return {}; std::vector<value_type> res; auto dfs = [&](auto dfs, node_pointer_type cur, int id, int p) -> void { if (int(res.size()) <= id) res.resize(id + 1); res[id] = node->_val; int np = p << lg_ary, nid = id + p; for (int d = 1; d < 1 << lg_ary; ++d, nid += p) { if (cur->_ch[d]) dfs(dfs, cur->_ch[d], nid, np); else return; } if (cur->_ch[0]) dfs(dfs, cur->_ch[0], nid, np); }; dfs(dfs, node, 0, 1); return res; } }; static void init_pool(int capacity) { node_type::pool = pool_type(capacity); } PersistentArray() = default; explicit PersistentArray(int n, const value_type& val = value_type{}) : PersistentArray(std::vector<value_type>(n, val)) {} PersistentArray(const std::vector<value_type>& init) : _n(init.size()), _root(node_type::build(init)) {} int size() const { return _n; } const value_type& get(int id) { return node_type::get(_root, id); } PersistentArray set(int id, const value_type& new_val) { return PersistentArray{ _n, node_type::set(_root, id, new_val) }; } value_type mut_set(int id, const value_type& new_val) { return node_type::mut_set(_root, id, new_val); } PersistentArray clone() { if (not _root) return PersistentArray { _n, _root }; return PersistentArray{ _n, node_type::clone(_root) }; } std::vector<value_type> dump() { return node_type::dump(_root); } private: int _n; node_pointer_type _root; explicit PersistentArray(int n, node_pointer_type root) : _n(n), _root(root) {} }; } // namespace suisen #line 8 "library/datastructure/union_find/persistent_union_find.hpp" namespace suisen { struct PersistentUnionFind { using array_type = PersistentArray<int, 4>; PersistentUnionFind() = default; explicit PersistentUnionFind(int n) : _n(n), _dat(_n, -1) {} static void init_pool(int capacity) { array_type::init_pool(capacity); } // Get the root of `x`. equivalent to `operator[](x)` int root(int x) { static std::vector<int> buf; while (true) { if (int r = _dat.get(x); r >= 0) buf.push_back(std::exchange(x, r)); else break; } while (buf.size()) _dat.mut_set(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`. std::pair<PersistentUnionFind, bool> merge(int x, int y) { x = root(x), y = root(y); if (x == y) return { *this, false }; int vx = _dat.get(x), vy = _dat.get(y); if (vx > vy) std::swap(x, y), std::swap(vx, vy); array_type new_dat = _dat; new_dat = new_dat.set(x, vx + vy); new_dat = new_dat.set(y, x); return { PersistentUnionFind(new_dat), 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.get(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; } std::vector<int> dump() { return _dat.dump(); } protected: int _n; array_type _dat; explicit PersistentUnionFind(array_type dat) : _n(dat.size()), _dat(dat) {} }; } // namespace suisen