graph/offline-dynamic-connectivity.hpp

View this file on GitHub
Last update: 2023-03-25 00:28:17+09:00
Include: #include "graph/offline-dynamic-connectivity.hpp"

Depends on

Verified with

verify/verify-yosupo-ds/yosupo-offline-dynamic-connectivity.test.cpp

Code

#pragma once

#include "../data-structure/rollback-union-find.hpp"
#include "../hashmap/hashmap.hpp"

struct OffLineDynamicConnectivity {
  int N, Q, segsz;
  RollbackUnionFind uf;
  vector<vector<pair<int, int>>> seg, qadd, qdel;
  HashMap<pair<int, int>, pair<int, int>> cnt;

  OffLineDynamicConnectivity(int n, int q)
      : N(n), Q(q), uf(n), qadd(q), qdel(q) {
    segsz = 1;
    while (segsz < Q) segsz *= 2;
    seg.resize(segsz * 2);
  }

  void add_edge(int t, int u, int v) { qadd[t].emplace_back(u, v); }
  void del_edge(int t, int u, int v) { qdel[t].emplace_back(u, v); }

  void build() {
    for (int i = 0; i < Q; i++) {
      for (auto& e : qadd[i]) {
        auto& dat = cnt[e];
        if (dat.second++ == 0) dat.first = i;
      }
      for (auto& e : qdel[i]) {
        auto& dat = cnt[e];
        if (--dat.second == 0) segment(e, dat.first, i);
      }
    }
    for (auto& [e, dat] : cnt) {
      if (dat.second != 0) segment(e, dat.first, Q);
    }
  }

  template <typename ADD, typename DEL, typename QUERY>
  void dfs(const ADD& add, const DEL& del, const QUERY& query, int id, int l,
           int r) {
    if (Q <= l) return;
    int state = uf.get_state();
    vector<pair<int, int>> es;
    for (auto& [u, v] : seg[id]) {
      if (!uf.same(u, v)) {
        uf.unite(u, v);
        add(u, v);
        es.emplace_back(u, v);
      }
    }
    if (l + 1 == r) {
      query(l);
    } else {
      dfs(add, del, query, id * 2 + 0, l, (l + r) >> 1);
      dfs(add, del, query, id * 2 + 1, (l + r) >> 1, r);
    }
    for (auto& [u, v] : es) del(u, v);
    uf.rollback(state);
  }

  template <typename ADD, typename DEL, typename QUERY>
  void run(const ADD& add, const DEL& del, const QUERY& query) {
    dfs(add, del, query, 1, 0, segsz);
  }

 private:
  void segment(pair<int, int>& e, int l, int r) {
    int L = l + segsz;
    int R = r + segsz;
    while (L < R) {
      if (L & 1) seg[L++].push_back(e);
      if (R & 1) seg[--R].push_back(e);
      L >>= 1, R >>= 1;
    }
  }
};

#line 2 "graph/offline-dynamic-connectivity.hpp"

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

struct RollbackUnionFind {
  vector<int> data;
  stack<pair<int, int> > history;
  int inner_snap;

  RollbackUnionFind(int sz) : inner_snap(0) { data.assign(sz, -1); }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    history.emplace(x, data[x]);
    history.emplace(y, data[y]);
    if (x == y) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if (data[k] < 0) return k;
    return find(data[k]);
  }

  int same(int x, int y) { return find(x) == find(y); }

  int size(int k) { return (-data[find(k)]); }

  void undo() {
    data[history.top().first] = history.top().second;
    history.pop();
    data[history.top().first] = history.top().second;
    history.pop();
  }

  void snapshot() { inner_snap = int(history.size() >> 1); }

  int get_state() { return int(history.size() >> 1); }

  void rollback(int state = -1) {
    if (state == -1) state = inner_snap;
    state <<= 1;
    assert(state <= (int)history.size());
    while (state < (int)history.size()) undo();
  }
};

/**
 * @brief RollbackつきUnion Find
 * @docs docs/data-structure/rollback-union-find.md
 */
#line 2 "hashmap/hashmap.hpp"

#line 2 "hashmap/hashmap-base.hpp"

#include <cstdint>
using namespace std;

namespace HashMapImpl {
using u32 = uint32_t;
using u64 = uint64_t;

template <typename Key, typename Data>
struct HashMapBase;

template <typename Key, typename Data>
struct itrB
    : iterator<bidirectional_iterator_tag, Data, ptrdiff_t, Data*, Data&> {
  using base =
      iterator<bidirectional_iterator_tag, Data, ptrdiff_t, Data*, Data&>;
  using ptr = typename base::pointer;
  using ref = typename base::reference;

  u32 i;
  HashMapBase<Key, Data>* p;

  explicit constexpr itrB() : i(0), p(nullptr) {}
  explicit constexpr itrB(u32 _i, HashMapBase<Key, Data>* _p) : i(_i), p(_p) {}
  explicit constexpr itrB(u32 _i, const HashMapBase<Key, Data>* _p)
      : i(_i), p(const_cast<HashMapBase<Key, Data>*>(_p)) {}
  friend void swap(itrB& l, itrB& r) { swap(l.i, r.i), swap(l.p, r.p); }
  friend bool operator==(const itrB& l, const itrB& r) { return l.i == r.i; }
  friend bool operator!=(const itrB& l, const itrB& r) { return l.i != r.i; }
  const ref operator*() const {
    return const_cast<const HashMapBase<Key, Data>*>(p)->data[i];
  }
  ref operator*() { return p->data[i]; }
  ptr operator->() const { return &(p->data[i]); }

  itrB& operator++() {
    assert(i != p->cap && "itr::operator++()");
    do {
      i++;
      if (i == p->cap) break;
      if (p->occupied_flag[i] && !p->deleted_flag[i]) break;
    } while (true);
    return (*this);
  }
  itrB operator++(int) {
    itrB it(*this);
    ++(*this);
    return it;
  }
  itrB& operator--() {
    do {
      i--;
      if (p->occupied_flag[i] && !p->deleted_flag[i]) break;
      assert(i != 0 && "itr::operator--()");
    } while (true);
    return (*this);
  }
  itrB operator--(int) {
    itrB it(*this);
    --(*this);
    return it;
  }
};

template <typename Key, typename Data>
struct HashMapBase {
  using u32 = uint32_t;
  using u64 = uint64_t;
  using iterator = itrB<Key, Data>;
  using itr = iterator;

 protected:
  template <typename K>
  inline u64 randomized(const K& key) const {
    return u64(key) ^ r;
  }

  template <typename K,
            enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr,
            enable_if_t<is_integral<K>::value, nullptr_t> = nullptr>
  inline u32 inner_hash(const K& key) const {
    return (randomized(key) * 11995408973635179863ULL) >> shift;
  }
  template <
      typename K, enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr,
      enable_if_t<is_integral<decltype(K::first)>::value, nullptr_t> = nullptr,
      enable_if_t<is_integral<decltype(K::second)>::value, nullptr_t> = nullptr>
  inline u32 inner_hash(const K& key) const {
    u64 a = randomized(key.first), b = randomized(key.second);
    a *= 11995408973635179863ULL;
    b *= 10150724397891781847ULL;
    return (a + b) >> shift;
  }
  template <typename K,
            enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr,
            enable_if_t<is_integral<typename K::value_type>::value, nullptr_t> =
                nullptr>
  inline u32 inner_hash(const K& key) const {
    static constexpr u64 mod = (1LL << 61) - 1;
    static constexpr u64 base = 950699498548472943ULL;
    u64 res = 0;
    for (auto& elem : key) {
      __uint128_t x = __uint128_t(res) * base + (randomized(elem) & mod);
      res = (x & mod) + (x >> 61);
    }
    __uint128_t x = __uint128_t(res) * base;
    res = (x & mod) + (x >> 61);
    if (res >= mod) res -= mod;
    return res >> (shift - 3);
  }

  template <typename D = Data,
            enable_if_t<is_same<D, Key>::value, nullptr_t> = nullptr>
  inline u32 hash(const D& dat) const {
    return inner_hash(dat);
  }
  template <
      typename D = Data,
      enable_if_t<is_same<decltype(D::first), Key>::value, nullptr_t> = nullptr>
  inline u32 hash(const D& dat) const {
    return inner_hash(dat.first);
  }

  template <typename D = Data,
            enable_if_t<is_same<D, Key>::value, nullptr_t> = nullptr>
  inline Key data_to_key(const D& dat) const {
    return dat;
  }
  template <
      typename D = Data,
      enable_if_t<is_same<decltype(D::first), Key>::value, nullptr_t> = nullptr>
  inline Key data_to_key(const D& dat) const {
    return dat.first;
  }

  void reallocate(u32 ncap) {
    vector<Data> ndata(ncap);
    vector<bool> nf(ncap);
    shift = 64 - __lg(ncap);
    for (u32 i = 0; i < cap; i++) {
      if (occupied_flag[i] && !deleted_flag[i]) {
        u32 h = hash(data[i]);
        while (nf[h]) h = (h + 1) & (ncap - 1);
        ndata[h] = move(data[i]);
        nf[h] = true;
      }
    }
    data.swap(ndata);
    occupied_flag.swap(nf);
    cap = ncap;
    occupied = s;
    deleted_flag.resize(cap);
    fill(std::begin(deleted_flag), std::end(deleted_flag), false);
  }

  inline bool extend_rate(u32 x) const { return x * 2 >= cap; }

  inline bool shrink_rate(u32 x) const {
    return HASHMAP_DEFAULT_SIZE < cap && x * 10 <= cap;
  }

  inline void extend() { reallocate(cap << 1); }

  inline void shrink() { reallocate(cap >> 1); }

 public:
  u32 cap, s, occupied;
  vector<Data> data;
  vector<bool> occupied_flag, deleted_flag;
  u32 shift;
  static u64 r;
  static constexpr uint32_t HASHMAP_DEFAULT_SIZE = 4;

  explicit HashMapBase()
      : cap(HASHMAP_DEFAULT_SIZE),
        s(0),
        occupied(0),
        data(cap),
        occupied_flag(cap),
        deleted_flag(cap),
        shift(64 - __lg(cap)) {}

  itr begin() const {
    u32 h = 0;
    while (h != cap) {
      if (occupied_flag[h] && !deleted_flag[h]) break;
      h++;
    }
    return itr(h, this);
  }
  itr end() const { return itr(this->cap, this); }

  friend itr begin(const HashMapBase& h) { return h.begin(); }
  friend itr end(const HashMapBase& h) { return h.end(); }

  itr find(const Key& key) const {
    u32 h = inner_hash(key);
    while (true) {
      if (occupied_flag[h] == false) return this->end();
      if (data_to_key(data[h]) == key) {
        if (deleted_flag[h] == true) return this->end();
        return itr(h, this);
      }
      h = (h + 1) & (cap - 1);
    }
  }

  bool contain(const Key& key) const { return find(key) != this->end(); }

  itr insert(const Data& d) {
    u32 h = hash(d);
    while (true) {
      if (occupied_flag[h] == false) {
        if (extend_rate(occupied + 1)) {
          extend();
          h = hash(d);
          continue;
        }
        data[h] = d;
        occupied_flag[h] = true;
        ++occupied, ++s;
        return itr(h, this);
      }
      if (data_to_key(data[h]) == data_to_key(d)) {
        if (deleted_flag[h] == true) {
          data[h] = d;
          deleted_flag[h] = false;
          ++s;
        }
        return itr(h, this);
      }
      h = (h + 1) & (cap - 1);
    }
  }

  // tips for speed up :
  // if return value is unnecessary, make argument_2 false.
  itr erase(itr it, bool get_next = true) {
    if (it == this->end()) return this->end();
    s--;
    if (!get_next) {
      this->deleted_flag[it.i] = true;
      if (shrink_rate(s)) shrink();
      return this->end();
    }
    itr nxt = it;
    nxt++;
    this->deleted_flag[it.i] = true;
    if (shrink_rate(s)) {
      Data d = data[nxt.i];
      shrink();
      it = find(data_to_key(d));
    }
    return nxt;
  }

  itr erase(const Key& key) { return erase(find(key)); }

  int count(const Key& key) { return find(key) == end() ? 0 : 1; }

  bool empty() const { return s == 0; }

  int size() const { return s; }

  void clear() {
    fill(std::begin(occupied_flag), std::end(occupied_flag), false);
    fill(std::begin(deleted_flag), std::end(deleted_flag), false);
    s = occupied = 0;
  }

  void reserve(int n) {
    if (n <= 0) return;
    n = 1 << min(23, __lg(n) + 2);
    if (cap < u32(n)) reallocate(n);
  }
};

template <typename Key, typename Data>
uint64_t HashMapBase<Key, Data>::r =
    chrono::duration_cast<chrono::nanoseconds>(
        chrono::high_resolution_clock::now().time_since_epoch())
        .count();

}  // namespace HashMapImpl

/**
 * @brief Hash Map(base)　(ハッシュマップ・基底クラス)
 */
#line 4 "hashmap/hashmap.hpp"

template <typename Key, typename Val>
struct HashMap : HashMapImpl::HashMapBase<Key, pair<Key, Val>> {
  using base = typename HashMapImpl::HashMapBase<Key, pair<Key, Val>>;
  using HashMapImpl::HashMapBase<Key, pair<Key, Val>>::HashMapBase;
  using Data = pair<Key, Val>;

  Val& operator[](const Key& k) {
    typename base::u32 h = base::inner_hash(k);
    while (true) {
      if (base::occupied_flag[h] == false) {
        if (base::extend_rate(base::occupied + 1)) {
          base::extend();
          h = base::hash(k);
          continue;
        }
        base::data[h].first = k;
        base::data[h].second = Val();
        base::occupied_flag[h] = true;
        ++base::occupied, ++base::s;
        return base::data[h].second;
      }
      if (base::data[h].first == k) {
        if (base::deleted_flag[h] == true) {
          base::data[h].second = Val();
          base::deleted_flag[h] = false;
          ++base::s;
        }
        return base::data[h].second;
      }
      h = (h + 1) & (base::cap - 1);
    }
  }

  typename base::itr emplace(const Key& key, const Val& val) {
    return base::insert(Data(key, val));
  }
};

/*
 * @brief ハッシュマップ(連想配列)
 * @docs docs/hashmap/hashmap.md
 **/
#line 5 "graph/offline-dynamic-connectivity.hpp"

struct OffLineDynamicConnectivity {
  int N, Q, segsz;
  RollbackUnionFind uf;
  vector<vector<pair<int, int>>> seg, qadd, qdel;
  HashMap<pair<int, int>, pair<int, int>> cnt;

  OffLineDynamicConnectivity(int n, int q)
      : N(n), Q(q), uf(n), qadd(q), qdel(q) {
    segsz = 1;
    while (segsz < Q) segsz *= 2;
    seg.resize(segsz * 2);
  }

  void add_edge(int t, int u, int v) { qadd[t].emplace_back(u, v); }
  void del_edge(int t, int u, int v) { qdel[t].emplace_back(u, v); }

  void build() {
    for (int i = 0; i < Q; i++) {
      for (auto& e : qadd[i]) {
        auto& dat = cnt[e];
        if (dat.second++ == 0) dat.first = i;
      }
      for (auto& e : qdel[i]) {
        auto& dat = cnt[e];
        if (--dat.second == 0) segment(e, dat.first, i);
      }
    }
    for (auto& [e, dat] : cnt) {
      if (dat.second != 0) segment(e, dat.first, Q);
    }
  }

  template <typename ADD, typename DEL, typename QUERY>
  void dfs(const ADD& add, const DEL& del, const QUERY& query, int id, int l,
           int r) {
    if (Q <= l) return;
    int state = uf.get_state();
    vector<pair<int, int>> es;
    for (auto& [u, v] : seg[id]) {
      if (!uf.same(u, v)) {
        uf.unite(u, v);
        add(u, v);
        es.emplace_back(u, v);
      }
    }
    if (l + 1 == r) {
      query(l);
    } else {
      dfs(add, del, query, id * 2 + 0, l, (l + r) >> 1);
      dfs(add, del, query, id * 2 + 1, (l + r) >> 1, r);
    }
    for (auto& [u, v] : es) del(u, v);
    uf.rollback(state);
  }

  template <typename ADD, typename DEL, typename QUERY>
  void run(const ADD& add, const DEL& del, const QUERY& query) {
    dfs(add, del, query, 1, 0, segsz);
  }

 private:
  void segment(pair<int, int>& e, int l, int r) {
    int L = l + segsz;
    int R = r + segsz;
    while (L < R) {
      if (L & 1) seg[L++].push_back(e);
      if (R & 1) seg[--R].push_back(e);
      L >>= 1, R >>= 1;
    }
  }
};

Nyaan's Library

This documentation is automatically generated by online-judge-tools/verification-helper

graph/offline-dynamic-connectivity.hpp

Depends on

Verified with

Code