完全永続Union-Find
(data-structure/persistent-union-find.hpp)

• View this file on GitHub
• Last update: 2020-12-05 07:59:51+09:00
• Include: #include "data-structure/persistent-union-find.hpp"

Depends on

• 永続配列 (data-structure/persistent-array.hpp)

Verified with

• verify/verify-yosupo-ds/yosupo-persistent-unionfind.test.cpp

Code

#pragma once

#include "./persistent-array.hpp"

struct PersistentUnionFind {
  PersistentArray<int> arr;
  using Node = decltype(arr)::Node;
  static Node *root;

  PersistentUnionFind(int N) : arr(vector<int>(N, -1)) { root = arr.root; }

  pair<int, int> find_with_size(int i, Node *r = root) {
    int n = arr.get(r, i);
    return n < 0 ? pair<int, int>{i, n} : find_with_size(n, r);
  }
  inline int find(int i, Node *r = root) { return find_with_size(i, r).first; }
  inline int size(int i, Node *r = root) { return -(find_with_size(i, r).second); }
  inline int same(int i, int j, Node *r = root) { return find(i, r) == find(j, r); }

  int unite(int i, int j, Node *r = root) {
    int is, js;
    tie(i, is) = find_with_size(i, r);
    tie(j, js) = find_with_size(j, r);
    if (i == j) return false;
    if (is > js) swap(i, j), swap(is, js);
    r = arr.update(r, i, is + js);
    r = arr.update(r, j, i);
    root = r;
    return true;
  }

  Node *get_root() const { return root; }
};
typename PersistentUnionFind::Node *PersistentUnionFind::root = nullptr;

/**
 * @brief 完全永続Union-Find
 */

#line 2 "data-structure/persistent-union-find.hpp"

#line 2 "data-structure/persistent-array.hpp"

template <typename T, int shift = 4>
struct PersistentArray {
  struct Node {
    Node *ns[1 << shift];
    Node() { memset(ns, 0, sizeof(ns)); }
    Node(const Node &other) { memcpy(ns, other.ns, sizeof(ns)); }
    Node(const Node *other) { memcpy(ns, other->ns, sizeof(ns)); }
  };
  inline Node *my_new() { return new Node(); }
  inline Node *my_new(const Node &other) { return new Node(other); }
  inline Node *my_new(const Node *other) { return new Node(other); }
  inline T *my_new_leaf(const T &val) { return new T{val}; }

  using i64 = long long;
  static constexpr int mask = (1 << shift) - 1;
  Node *root;
  int depth;
  T ID;

  PersistentArray() {}

  PersistentArray(i64 MAX, T ID_ = T(0)) : root(my_new()), depth(0), ID(ID_) {
    while (MAX) ++depth, MAX >>= shift;
  }

  PersistentArray(const vector<T> &v, T ID_ = T(0))
      : root(my_new()), depth(0), ID(ID_) {
    i64 MAX = v.size();
    while (MAX) ++depth, MAX >>= shift;
    for (int i = 0; i < (int)v.size(); i++) {
      Node *n = root;
      for (int k = i, d = depth; d; d--) {
        if (!(n->ns[k & mask])) {
          if (d == 1)
            n->ns[k & mask] = reinterpret_cast<Node *>(my_new_leaf(v[i]));
          else
            n->ns[k & mask] = my_new();
        }
        n = n->ns[k & mask];
        k >>= shift;
      }
    }
  }

  T get(Node *n, i64 k) const {
    for (int i = depth; i; --i) {
      n = n ? n->ns[k & mask] : nullptr;
      k >>= shift;
    }
    return n ? *reinterpret_cast<T *>(n) : ID;
  }
  T get(i64 k) const { return get(root, k); }

  Node *update(Node *n, i64 k, const T &val) {
    stack<pair<Node *, int>> st;
    for (int i = depth; i; --i) {
      st.emplace(n, k & mask);
      n = n ? n->ns[k & mask] : nullptr;
      k >>= shift;
    }
    Node *chd = reinterpret_cast<Node *>(my_new_leaf(val));
    while (!st.empty()) {
      Node *par;
      int k;
      tie(par, k) = st.top();
      st.pop();
      Node *nxt = par ? my_new(par) : my_new();
      nxt->ns[k] = chd;
      chd = nxt;
    }
    return root = chd;
  }
  Node *update(i64 k, const T &val) { return update(root, k, val); }
};

/**
 * @brief 永続配列
 */
#line 4 "data-structure/persistent-union-find.hpp"

struct PersistentUnionFind {
  PersistentArray<int> arr;
  using Node = decltype(arr)::Node;
  static Node *root;

  PersistentUnionFind(int N) : arr(vector<int>(N, -1)) { root = arr.root; }

  pair<int, int> find_with_size(int i, Node *r = root) {
    int n = arr.get(r, i);
    return n < 0 ? pair<int, int>{i, n} : find_with_size(n, r);
  }
  inline int find(int i, Node *r = root) { return find_with_size(i, r).first; }
  inline int size(int i, Node *r = root) { return -(find_with_size(i, r).second); }
  inline int same(int i, int j, Node *r = root) { return find(i, r) == find(j, r); }

  int unite(int i, int j, Node *r = root) {
    int is, js;
    tie(i, is) = find_with_size(i, r);
    tie(j, js) = find_with_size(j, r);
    if (i == j) return false;
    if (is > js) swap(i, j), swap(is, js);
    r = arr.update(r, i, is + js);
    r = arr.update(r, j, i);
    root = r;
    return true;
  }

  Node *get_root() const { return root; }
};
typename PersistentUnionFind::Node *PersistentUnionFind::root = nullptr;

/**
 * @brief 完全永続Union-Find
 */

Back to top page