Partially persistent disjoint set union (tools/partially_persistent_dsu.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-01-28 13:52:56+09:00
Include: #include "tools/partially_persistent_dsu.hpp"

Given an undirected graph, it processes the following queries in $O(\log(n))$ time.

Edge addition
Deciding whether given two vertices were in the same connected component at the specified time

Each connected component internally has a representative vertex.

License

Author

anqooqie

Constructor

partially_persistent_dsu d(int n);

It creates an undirected graph with $n$ vertices and $0$ edges.

Constraints

$n \geq 0$

Time Complexity

$O(n)$

now

int d.now();

It returns the number of times that d.merge has been called so far.

Constraints

None

Time Complexity

$O(1)$

merge

int d.merge(int a, int b);

It adds an edge $(a, b)$.

If the vertices $a$ and $b$ were in the same connected component, it returns the representative of this connected component. Otherwise, it returns the representative of the new connected component.

Constraints

$0 \leq a < n$
$0 \leq b < n$

Time Complexity

$O(\log n)$

same

bool d.same(int t, int a, int b);

It returns whether the vertices $a$ and $b$ were in the same connected component at the time when d.now() == t.

Constraints

$0 \leq t \leq$ d.now()
$0 \leq a < n$
$0 \leq b < n$

Time Complexity

$O(\log n)$

leader

int d.leader(int t, int a);

It returns the representative of the connected component that contained the vertex $a$ at the time when d.now() == t.

Constraints

$0 \leq t \leq$ d.now()
$0 \leq a < n$

Time Complexity

$O(\log n)$

size

int d.size(int t, int a);

It returns the size of the connected component that contained the vertex $a$ at the time when d.now() == t.

Constraints

$0 \leq t \leq$ d.now()
$0 \leq a < n$

Time Complexity

$O(\log n)$

groups

std::vector<std::vector<int>> d.groups(int t);

It divides the graph at the time when d.now() == t into connected components and returns the list of them.

More precisely, it returns the list of the “list of the vertices in a connected component”. Both of the orders of the connected components and the vertices are undefined.

Constraints

$0 \leq t \leq$ d.now()

Time Complexity

$O(n)$

Depends on

std::less by first (tools/less_by_first.hpp)

Verified with

tests/partially_persistent_dsu.test.cpp

Code

#ifndef TOOLS_PARTIALLY_PERSISTENT_DSU_HPP
#define TOOLS_PARTIALLY_PERSISTENT_DSU_HPP

#include <vector>
#include <utility>
#include <limits>
#include <cassert>
#include <algorithm>
#include <queue>
#include "tools/less_by_first.hpp"

namespace tools {
  class partially_persistent_dsu {
  private:
    int m_now;
    ::std::vector<::std::pair<int, int>> m_parents;
    ::std::vector<int> m_ranks;
    ::std::vector<::std::vector<::std::pair<int, int>>> m_sizes;

    int size() const {
      return this->m_parents.size();
    }

  public:
    partially_persistent_dsu() = default;
    partially_persistent_dsu(const ::tools::partially_persistent_dsu&) = default;
    partially_persistent_dsu(::tools::partially_persistent_dsu&&) = default;
    ~partially_persistent_dsu() = default;
    ::tools::partially_persistent_dsu& operator=(const ::tools::partially_persistent_dsu&) = default;
    ::tools::partially_persistent_dsu& operator=(::tools::partially_persistent_dsu&&) = default;

    explicit partially_persistent_dsu(const int n) :
      m_now(0),
      m_parents(n, ::std::make_pair(::std::numeric_limits<int>::max(), -1)),
      m_ranks(n, 0),
      m_sizes(n, ::std::vector<::std::pair<int, int>>{::std::make_pair(0, 1)}) {
    }

    int now() const {
      return this->m_now;
    }

    int leader(const int t, const int x) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());

      return t < this->m_parents[x].first ? x : this->leader(t, this->m_parents[x].second);
    }

    bool same(const int t, const int x, const int y) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      return this->leader(t, x) == this->leader(t, y);
    }

    int merge(int x, int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      ++this->m_now;

      x = this->leader(this->m_now, x);
      y = this->leader(this->m_now, y);
      if (x == y) return x;

      if (this->m_ranks[x] < this->m_ranks[y]) ::std::swap(x, y);

      this->m_parents[y] = ::std::make_pair(this->m_now, x);
      if (this->m_ranks[x] == this->m_ranks[y]) ++this->m_ranks[x];
      this->m_sizes[x].emplace_back(this->m_now, this->m_sizes[x].back().second + this->m_sizes[y].back().second);

      return x;
    }

    int size(const int t, int x) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());

      x = this->leader(t, x);
      auto it = ::std::upper_bound(this->m_sizes[x].begin(), this->m_sizes[x].end(), ::std::make_pair(t, 0), ::tools::less_by_first());
      --it;
      return it->second;
    }

    ::std::vector<::std::vector<int>> groups(const int t) const {
      assert(0 <= t && t <= this->m_now);

      ::std::vector<::std::vector<int>> graph(this->size());
      for (int i = 0; i < this->size(); ++i) {
        if (this->m_parents[i].first <= t) graph[this->m_parents[i].second].push_back(i);
      }

      ::std::vector<::std::vector<int>> res(this->size());
      for (int root = 0; root < this->size(); ++root) {
        if (t < this->m_parents[root].first) {
          ::std::queue<int> queue({root});
          while (!queue.empty()) {
            const auto here = queue.front();
            queue.pop();
            res[root].push_back(here);
            for (const auto next : graph[here]) {
              queue.push(next);
            }
          }
        }
      }

      res.erase(::std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }
  };
}

#endif

#line 1 "tools/partially_persistent_dsu.hpp"



#include <vector>
#include <utility>
#include <limits>
#include <cassert>
#include <algorithm>
#include <queue>
#line 1 "tools/less_by_first.hpp"



#line 5 "tools/less_by_first.hpp"

namespace tools {

  class less_by_first {
  public:
    template <class T1, class T2>
    bool operator()(const ::std::pair<T1, T2>& x, const ::std::pair<T1, T2>& y) const {
      return x.first < y.first;
    }
  };
}


#line 11 "tools/partially_persistent_dsu.hpp"

namespace tools {
  class partially_persistent_dsu {
  private:
    int m_now;
    ::std::vector<::std::pair<int, int>> m_parents;
    ::std::vector<int> m_ranks;
    ::std::vector<::std::vector<::std::pair<int, int>>> m_sizes;

    int size() const {
      return this->m_parents.size();
    }

  public:
    partially_persistent_dsu() = default;
    partially_persistent_dsu(const ::tools::partially_persistent_dsu&) = default;
    partially_persistent_dsu(::tools::partially_persistent_dsu&&) = default;
    ~partially_persistent_dsu() = default;
    ::tools::partially_persistent_dsu& operator=(const ::tools::partially_persistent_dsu&) = default;
    ::tools::partially_persistent_dsu& operator=(::tools::partially_persistent_dsu&&) = default;

    explicit partially_persistent_dsu(const int n) :
      m_now(0),
      m_parents(n, ::std::make_pair(::std::numeric_limits<int>::max(), -1)),
      m_ranks(n, 0),
      m_sizes(n, ::std::vector<::std::pair<int, int>>{::std::make_pair(0, 1)}) {
    }

    int now() const {
      return this->m_now;
    }

    int leader(const int t, const int x) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());

      return t < this->m_parents[x].first ? x : this->leader(t, this->m_parents[x].second);
    }

    bool same(const int t, const int x, const int y) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      return this->leader(t, x) == this->leader(t, y);
    }

    int merge(int x, int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      ++this->m_now;

      x = this->leader(this->m_now, x);
      y = this->leader(this->m_now, y);
      if (x == y) return x;

      if (this->m_ranks[x] < this->m_ranks[y]) ::std::swap(x, y);

      this->m_parents[y] = ::std::make_pair(this->m_now, x);
      if (this->m_ranks[x] == this->m_ranks[y]) ++this->m_ranks[x];
      this->m_sizes[x].emplace_back(this->m_now, this->m_sizes[x].back().second + this->m_sizes[y].back().second);

      return x;
    }

    int size(const int t, int x) const {
      assert(0 <= t && t <= this->m_now);
      assert(0 <= x && x < this->size());

      x = this->leader(t, x);
      auto it = ::std::upper_bound(this->m_sizes[x].begin(), this->m_sizes[x].end(), ::std::make_pair(t, 0), ::tools::less_by_first());
      --it;
      return it->second;
    }

    ::std::vector<::std::vector<int>> groups(const int t) const {
      assert(0 <= t && t <= this->m_now);

      ::std::vector<::std::vector<int>> graph(this->size());
      for (int i = 0; i < this->size(); ++i) {
        if (this->m_parents[i].first <= t) graph[this->m_parents[i].second].push_back(i);
      }

      ::std::vector<::std::vector<int>> res(this->size());
      for (int root = 0; root < this->size(); ++root) {
        if (t < this->m_parents[root].first) {
          ::std::queue<int> queue({root});
          while (!queue.empty()) {
            const auto here = queue.front();
            queue.pop();
            res[root].push_back(here);
            for (const auto next : graph[here]) {
              queue.push(next);
            }
          }
        }
      }

      res.erase(::std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }
  };
}