動的Union Find
(data-structure/dynamic-union-find.hpp)

• View this file on GitHub
• Last update: 2023-03-25 00:28:17+09:00
• Include: #include "data-structure/dynamic-union-find.hpp"

動的Union Find

概要

Union Findの動的版。配列を使っていた部分を連想配列に変えることで空間計算量を削減している。

使い方

• UnionFind(int sz)：サイズ$sz$のUnionFindを生成する。計算量$\mathrm{O}(1)$
• unite(int x, int y)：xとyをマージする。返り値はマージに成功したらtrue、失敗したらfalseを返す。計算量$\mathrm{O}(\alpha(n))$($n$はUnionFindのサイズ)
• find(int k)：kの根を返す。計算量$\mathrm{O}(\alpha(n))$
• same(int x, int y)：xとyが同じ連結成分に所属しているかを返す。計算量$\mathrm{O}(\alpha(n))$
• size(int k)：xを含む連結成分のサイズを返す。

Depends on

• Hash Map(base)　(ハッシュマップ・基底クラス) (hashmap/hashmap-base.hpp)
• ハッシュマップ(連想配列) (hashmap/hashmap.hpp)

Verified with

• verify/verify-aoj-dsl/aoj-dsl-1-a-dynamic.test.cpp
• verify/verify-aoj-other/aoj-2995-hashmap.test.cpp

Code

#pragma once

#include "../hashmap/hashmap.hpp"

struct DynamicUnionFind {
  HashMap<int, int> m;
  DynamicUnionFind() = default;

  int data(int k) {
    auto it = m.find(k);
    return it == m.end() ? m[k] = -1 : it->second;
  }
  int find(int k) {
    int n = data(k);
    return n < 0 ? k : m[k] = find(n);
  }

  int unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    auto itx = m.find(x), ity = m.find(y);
    if (itx->second > ity->second) swap(itx, ity), swap(x, y);
    itx->second += ity->second;
    ity->second = x;
    return true;
  }

  template <typename F>
  int unite(int x, int y, const F& f) {
    x = find(x), y = find(y);
    if (x == y) return false;
    auto itx = m.find(x), ity = m.find(y);
    if (itx->second > ity->second) swap(itx, ity), swap(x, y);
    itx->second += ity->second;
    ity->second = x;
    f(x, y);
    return true;
  }

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

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

  void clear() { m.clear(); }
};

/**
 * @brief 動的Union Find
 * @docs docs/data-structure/dynamic-union-find.md
 */

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

#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 4 "data-structure/dynamic-union-find.hpp"

struct DynamicUnionFind {
  HashMap<int, int> m;
  DynamicUnionFind() = default;

  int data(int k) {
    auto it = m.find(k);
    return it == m.end() ? m[k] = -1 : it->second;
  }
  int find(int k) {
    int n = data(k);
    return n < 0 ? k : m[k] = find(n);
  }

  int unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    auto itx = m.find(x), ity = m.find(y);
    if (itx->second > ity->second) swap(itx, ity), swap(x, y);
    itx->second += ity->second;
    ity->second = x;
    return true;
  }

  template <typename F>
  int unite(int x, int y, const F& f) {
    x = find(x), y = find(y);
    if (x == y) return false;
    auto itx = m.find(x), ity = m.find(y);
    if (itx->second > ity->second) swap(itx, ity), swap(x, y);
    itx->second += ity->second;
    ity->second = x;
    f(x, y);
    return true;
  }

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

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

  void clear() { m.clear(); }
};

/**
 * @brief 動的Union Find
 * @docs docs/data-structure/dynamic-union-find.md
 */

Back to top page