ds/unionfind/dynamic_unionfind.hpp

• View this file on GitHub
• Last update: 2023-08-19 23:46:31+09:00
• Include: #include "ds/unionfind/dynamic_unionfind.hpp"

Depends on

• ds/dynamic_array.hpp

Verified with

• test/library_checker/datastructure/persistent_unionfind.test.cpp

Code

#include "ds/dynamic_array.hpp"


template <bool PERSISTENT, int NODES>
struct Dynamic_UnionFind {
  // 経路圧縮なし

  Dynamic_Array<int, PERSISTENT, NODES> PA;
  using np = typename decltype(PA)::np;

  Dynamic_UnionFind() : PA(-1) {}

  np new_root() { return PA.new_root(); }

  int root(np c, int x) {
    while (1) {
      int p = PA.get(c, x);
      assert(x != p);
      if (p < 0) break;
      x = p;
    }
    return x;
  }

  pair<np, bool> merge(np c, int x, int y) {
    x = root(c, x), y = root(c, y);
    if (x == y) return {c, false};
    if (-PA.get(c, x) < -PA.get(c, y)) swap(x, y);
    int new_sz = PA.get(c, x) + PA.get(c, y);
    c = PA.set(c, x, new_sz);
    assert(PA.get(c, x) == new_sz);
    c = PA.set(c, y, x);
    assert(PA.get(c, y) == x);
    return {c, true};
  }

  ll size(np c, int x) { return -PA.get(c, root(c, x)); }
};

#line 2 "ds/dynamic_array.hpp"

template <typename T, bool PERSISTENT, int NODES>
struct Dynamic_Array {
  static constexpr int LOG = 4;
  static constexpr int MASK = (1 << LOG) - 1;
  struct Node {
    T x;
    Node* ch[1 << LOG] = {};
  };
  Node* pool;
  int pid;
  using np = Node*;
  const T x0;

  Dynamic_Array(T default_value) : pid(0), x0(default_value) {
    pool = new Node[NODES];
  }

  np new_root() {
    pool[pid].x = x0;
    fill(pool[pid].ch, pool[pid].ch + (1 << LOG), nullptr);
    return &(pool[pid++]);
  }

  np new_node(vc<T> dat) {
    np root = new_root();
    FOR(i, len(dat)) root = set(root, i, dat[i], false);
    return root;
  }

  T get(np c, int idx) {
    if (!c) return x0;
    if (idx == 0) return c->x;
    return get(c->ch[idx & MASK], (idx - 1) >> LOG);
  }

  np set(np c, int idx, T x, bool make_copy = true) {
    c = (c ? copy_node(c, make_copy) : new_root());
    if (idx == 0) {
      c->x = x;
      return c;
    }
    c->ch[idx & MASK] = set(c->ch[idx & MASK], (idx - 1) >> LOG, x);
    return c;
  }

private:
  np copy_node(np c, bool make_copy) {
    if (!make_copy || !PERSISTENT) return c;
    pool[pid].x = c->x;
    FOR(k, (1 << LOG)) pool[pid].ch[k] = c->ch[k];
    return &(pool[pid++]);
  }
};
#line 2 "ds/unionfind/dynamic_unionfind.hpp"

template <bool PERSISTENT, int NODES>
struct Dynamic_UnionFind {
  // 経路圧縮なし

  Dynamic_Array<int, PERSISTENT, NODES> PA;
  using np = typename decltype(PA)::np;

  Dynamic_UnionFind() : PA(-1) {}

  np new_root() { return PA.new_root(); }

  int root(np c, int x) {
    while (1) {
      int p = PA.get(c, x);
      assert(x != p);
      if (p < 0) break;
      x = p;
    }
    return x;
  }

  pair<np, bool> merge(np c, int x, int y) {
    x = root(c, x), y = root(c, y);
    if (x == y) return {c, false};
    if (-PA.get(c, x) < -PA.get(c, y)) swap(x, y);
    int new_sz = PA.get(c, x) + PA.get(c, y);
    c = PA.set(c, x, new_sz);
    assert(PA.get(c, x) == new_sz);
    c = PA.set(c, y, x);
    assert(PA.get(c, y) == x);
    return {c, true};
  }

  ll size(np c, int x) { return -PA.get(c, root(c, x)); }
};

Back to top page