Potentialized disjoint set union (tools/pdsu.hpp)

Given a group $(G, \cdot)$ and an unknown sequence $(a_0, a_1, \ldots, a_{n - 1}) \in G^n$, it processes the following queries in $O(\alpha(n))$ time (amortized).

Accepting the information $a_x = a_y \cdot w$
Reporting $a_y^{-1} \cdot a_x$

License

Author

anqooqie

Constructor

template <typename G = tools::group::plus<long long>>
pdsu<G> d(int n);

It creates an unknown sequence $(a_0, a_1, \ldots, a_{n - 1}) \in G^n$.

Constraints

$n \geq 0$
$\forall a \in G. \forall b \in G. \forall c \in G. (a \cdot b) \cdot c = a \cdot (b \cdot c)$
$\forall a \in G. e \cdot a = a \cdot e = a$ where $e$ is G::e()
$\forall a \in G. a^{-1} \cdot a = a \cdot a^{-1} = e$ where $e$ is G::e()

Time Complexity

$O(n)$

merge

int d.merge(int x, int y, typename G::T w);

It accepts the information $a_x = a_y \cdot w$.

Constraints

$0 \leq x < n$
$0 \leq y < n$

Time Complexity

$O(\alpha(n))$ amortized

diff

enum class pdsu_diff {
  known,
  unknown,
  inconsistent
};
std::pair<tools::pdsu_diff, typename G::T> d.diff(int x, int y);

If $a_y^{-1} \cdot a_x$ can be calculated consistently, it returns $(\mathrm{known}, a_y^{-1} \cdot a_x)$. If $a_y^{-1} \cdot a_x$ is still unknown under the information accepted so far, it returns $(\mathrm{unknown}, e)$ where $e$ is G::e(). If it turns out that the consistent value of $a_y^{-1} \cdot a_x$ cannot be obtained, it returns $(\mathrm{inconsistent}, e)$ where $e$ is G::e().

Constraints

$0 \leq x < n$
$0 \leq y < n$

Time Complexity

$O(\alpha(n))$ amortized

same

bool d.same(int x, int y);

If $a_y^{-1} \cdot a_x$ is still unknown under the information accepted so far, it returns false. Otherwise, it returns true.

Constraints

$0 \leq x < n$
$0 \leq y < n$

Time Complexity

$O(\alpha(n))$ amortized

leader

int d.leader(int x);

If an undirected graph with $n$ vertices is given and we connect the vertices $y$ and $z$ if and only if same(y, z) holds, the graph can be divided into some connected components. It returns the reprensative vertex of the connected component which contains $x$.

Constraints

$0 \leq x < n$

Time Complexity

$O(\alpha(n))$ amortized

size

int d.size(int x);

If an undirected graph with $n$ vertices is given and we connect the vertices $y$ and $z$ if and only if same(y, z) holds, the graph can be divided into some connected components. It returns the size of the connected component which contains $x$.

Constraints

$0 \leq x < n$

Time Complexity

$O(\alpha(n))$ amortized

groups

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

Constraints

None

Time Complexity

$O(n)$

Depends on

Typical groups (tools/group.hpp)

Verified with

tests/pdsu.test.cpp

Code

#ifndef TOOLS_PDSU_HPP
#define TOOLS_PDSU_HPP

#include <vector>
#include <cassert>
#include <numeric>
#include <utility>
#include "tools/group.hpp"

namespace tools {
  enum class pdsu_diff {
    known,
    unknown,
    inconsistent
  };

  template <typename G = ::tools::group::plus<long long>>
  class pdsu {
  private:
    using T = typename G::T;

    ::std::vector<int> m_parents;
    ::std::vector<int> m_sizes;
    ::std::vector<T> m_diffs;
    ::std::vector<bool> m_consistent;

  public:
    explicit pdsu(const int n) :
      m_parents(n),
      m_sizes(n, 1),
      m_diffs(n, G::e()),
      m_consistent(n, true) {
      assert(n >= 0);
      ::std::iota(this->m_parents.begin(), this->m_parents.end(), 0);
    }

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

    int leader(const int x) {
      assert(0 <= x && x < this->size());
      if (this->m_parents[x] == x) {
        return x;
      }
      const auto r = this->leader(this->m_parents[x]);
      if (this->m_consistent[r]) {
        this->m_diffs[x] = G::op(this->m_diffs[this->m_parents[x]], this->m_diffs[x]);
      }
      return this->m_parents[x] = r;
    }

    ::std::pair<::tools::pdsu_diff, T> diff(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());
      const auto x_r = this->leader(x);
      const auto y_r = this->leader(y);
      if (x_r == y_r) {
        if (this->m_consistent[x_r]) {
          return ::std::make_pair(::tools::pdsu_diff::known, G::op(G::inv(this->m_diffs[y]), this->m_diffs[x]));
        } else {
          return ::std::make_pair(::tools::pdsu_diff::inconsistent, G::e());
        }
      } else {
        return ::std::make_pair(::tools::pdsu_diff::unknown, G::e());
      }
    }

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

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

      auto x_r = this->leader(x);
      auto y_r = this->leader(y);

      if (x_r == y_r) {
        this->m_consistent[x_r] = (this->m_consistent[x_r] && this->m_diffs[x] == G::op(this->m_diffs[y], w));
        return x_r;
      }

      if (this->m_sizes[x_r] < this->m_sizes[y_r]) {
        ::std::swap(x, y);
        w = G::inv(w);
        ::std::swap(x_r, y_r);
      }
      this->m_parents[y_r] = x_r;
      this->m_sizes[x_r] += this->m_sizes[y_r];
      if (this->m_consistent[x_r] = (this->m_consistent[x_r] && this->m_consistent[y_r])) {
        this->m_diffs[y_r] = G::op(G::op(this->m_diffs[x], G::inv(w)), G::inv(this->m_diffs[y]));
      }
      return x_r;
    }

    int size(const int x) {
      assert(0 <= x && x < this->size());
      return this->m_sizes[this->leader(x)];
    }

    ::std::vector<::std::vector<int>> groups() {
      ::std::vector<int> group_indices(this->size(), -1);
      int next_group_index = 0;
      for (int i = 0; i < this->size(); ++i) {
        if (group_indices[this->leader(i)] == -1) {
          group_indices[this->leader(i)] = next_group_index;
          ++next_group_index;
        }
      }

      ::std::vector<::std::vector<int>> groups(next_group_index);
      for (int i = 0; i < this->size(); ++i) {
        groups[group_indices[this->leader(i)]].push_back(i);
      }

      return groups;
    }
  };
}

#endif

#line 1 "tools/pdsu.hpp"



#include <vector>
#include <cassert>
#include <numeric>
#include <utility>
#line 1 "tools/group.hpp"



namespace tools {
  namespace group {
    template <typename G>
    struct plus {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs + rhs;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& v) {
        return -v;
      }
    };

    template <typename G>
    struct multiplies {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
      static T inv(const T& v) {
        return e() / v;
      }
    };

    template <typename G>
    struct bit_xor {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs ^ rhs;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& v) {
        return v;
      }
    };
  }
}


#line 9 "tools/pdsu.hpp"

namespace tools {
  enum class pdsu_diff {
    known,
    unknown,
    inconsistent
  };

  template <typename G = ::tools::group::plus<long long>>
  class pdsu {
  private:
    using T = typename G::T;

    ::std::vector<int> m_parents;
    ::std::vector<int> m_sizes;
    ::std::vector<T> m_diffs;
    ::std::vector<bool> m_consistent;

  public:
    explicit pdsu(const int n) :
      m_parents(n),
      m_sizes(n, 1),
      m_diffs(n, G::e()),
      m_consistent(n, true) {
      assert(n >= 0);
      ::std::iota(this->m_parents.begin(), this->m_parents.end(), 0);
    }

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

    int leader(const int x) {
      assert(0 <= x && x < this->size());
      if (this->m_parents[x] == x) {
        return x;
      }
      const auto r = this->leader(this->m_parents[x]);
      if (this->m_consistent[r]) {
        this->m_diffs[x] = G::op(this->m_diffs[this->m_parents[x]], this->m_diffs[x]);
      }
      return this->m_parents[x] = r;
    }

    ::std::pair<::tools::pdsu_diff, T> diff(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());
      const auto x_r = this->leader(x);
      const auto y_r = this->leader(y);
      if (x_r == y_r) {
        if (this->m_consistent[x_r]) {
          return ::std::make_pair(::tools::pdsu_diff::known, G::op(G::inv(this->m_diffs[y]), this->m_diffs[x]));
        } else {
          return ::std::make_pair(::tools::pdsu_diff::inconsistent, G::e());
        }
      } else {
        return ::std::make_pair(::tools::pdsu_diff::unknown, G::e());
      }
    }

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

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

      auto x_r = this->leader(x);
      auto y_r = this->leader(y);

      if (x_r == y_r) {
        this->m_consistent[x_r] = (this->m_consistent[x_r] && this->m_diffs[x] == G::op(this->m_diffs[y], w));
        return x_r;
      }

      if (this->m_sizes[x_r] < this->m_sizes[y_r]) {
        ::std::swap(x, y);
        w = G::inv(w);
        ::std::swap(x_r, y_r);
      }
      this->m_parents[y_r] = x_r;
      this->m_sizes[x_r] += this->m_sizes[y_r];
      if (this->m_consistent[x_r] = (this->m_consistent[x_r] && this->m_consistent[y_r])) {
        this->m_diffs[y_r] = G::op(G::op(this->m_diffs[x], G::inv(w)), G::inv(this->m_diffs[y]));
      }
      return x_r;
    }

    int size(const int x) {
      assert(0 <= x && x < this->size());
      return this->m_sizes[this->leader(x)];
    }

    ::std::vector<::std::vector<int>> groups() {
      ::std::vector<int> group_indices(this->size(), -1);
      int next_group_index = 0;
      for (int i = 0; i < this->size(); ++i) {
        if (group_indices[this->leader(i)] == -1) {
          group_indices[this->leader(i)] = next_group_index;
          ++next_group_index;
        }
      }

      ::std::vector<::std::vector<int>> groups(next_group_index);
      for (int i = 0; i < this->size(); ++i) {
        groups[group_indices[this->leader(i)]].push_back(i);
      }

      return groups;
    }
  };
}