Union-Find(完全永続) (src/DataStructure/UnionFind_Persistent.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-09-21 21:45:32+09:00
• Include: #include "src/DataStructure/UnionFind_Persistent.hpp"

経路圧縮なし

計算量

$O(\log N)$

Verify

• CODE THANKS FESTIVAL 2017 H - Union Sets

Depends on

• 永続配列 (src/DataStructure/PersistentArray.hpp)

Verified with

• test/yosupo/persistent_unionfind.test.cpp

Code

#pragma once
#include "src/DataStructure/PersistentArray.hpp"
struct UnionFind_Persistent {
 PersistentArray<int, 64> par;
 UnionFind_Persistent() {}
 UnionFind_Persistent(int n): par(n, -1) {}
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par.get(u) > par.get(v)) std::swap(u, v);
  par[u]+= par.get(v), par[v]= u;
  return true;
 }
 bool connected(int u, int v) const { return leader(u) == leader(v); }
 int leader(int u) const { return par.get(u) < 0 ? u : leader(par.get(u)); }
 int size(int u) const { return -par.get(leader(u)); }
};

#line 2 "src/DataStructure/PersistentArray.hpp"
#include <vector>
template <class T, size_t M= 8> class PersistentArray {
 struct Node {
  T val;
  Node *ch[M];
 } *root;
 T get(Node *t, size_t k) const { return t ? (k ? get(t->ch[(k - 1) % M], (k - 1) / M) : t->val) : T(); }
 bool is_null(Node *t, size_t k) const { return t ? (k ? is_null(t->ch[(k - 1) % M], (k - 1) / M) : false) : true; }
 template <bool persistent= true> T &at(Node *&t, size_t k) {
  if (!t) t= new Node();
  else if constexpr (persistent) t= new Node(*t);
  return k ? at<persistent>(t->ch[(k - 1) % M], (k - 1) / M) : t->val;
 }
public:
 PersistentArray(): root(nullptr) {}
 PersistentArray(size_t n, T v): root(nullptr) {
  for (size_t i= n; i--;) at<false>(root, i)= v;
 }
 PersistentArray(T *bg, T *ed): root(nullptr) {
  for (size_t i= ed - bg; i--;) at<false>(root, i)= *(bg + i);
 }
 PersistentArray(const std::vector<T> &ar): PersistentArray(ar.data(), ar.data() + ar.size()) {}
 bool is_null(size_t k) const { return is_null(root, k); }
 T get(size_t k) const { return get(root, k); }
 T &at(size_t k) { return at<true>(root, k); }
 T &operator[](size_t k) { return at(k); }
 T operator[](size_t k) const { return get(k); }
};
#line 3 "src/DataStructure/UnionFind_Persistent.hpp"
struct UnionFind_Persistent {
 PersistentArray<int, 64> par;
 UnionFind_Persistent() {}
 UnionFind_Persistent(int n): par(n, -1) {}
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par.get(u) > par.get(v)) std::swap(u, v);
  par[u]+= par.get(v), par[v]= u;
  return true;
 }
 bool connected(int u, int v) const { return leader(u) == leader(v); }
 int leader(int u) const { return par.get(u) < 0 ? u : leader(par.get(u)); }
 int size(int u) const { return -par.get(leader(u)); }
};

Back to top page