Disjoint set union (tools/dsu.hpp)

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

Edge addition
Deciding whether given two vertices are in the same connected component

Each connected component internally has a representative vertex.

When two connected components are merged by edge addition, the representative of the larger connected component becomes the representative of the new connected component.

License

Author

anqooqie

Constructor

dsu d(int n);

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

Constraints

$n \geq 0$

Time Complexity

$O(n)$

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 the connected component. Otherwise, the representative of the larger (or former when the two have the same size) connected component becomes the representative of the new connected component, and it returns the new representative.

Constraints

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

Time Complexity

$O(\alpha(n))$ amortized

same

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

It returns whether the vertices $a$ and $b$ are in the same connected component.

Constraints

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

Time Complexity

$O(\alpha(n))$ amortized

leader

int d.leader(int a);

It returns the representative of the connected component that contains the vertex $a$.

Constraints

$0 \leq a < n$

Time Complexity

$O(\alpha(n))$ amortized

size

int d.size(int a);

It returns the size of the connected component that contains the vertex $a$.

Constraints

$0 \leq a < n$

Time Complexity

$O(\alpha(n))$ amortized

groups

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

It divides the graph 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

None

Time Complexity

$O(n)$

Verified with

tests/dsu.test.cpp

Code

#ifndef TOOLS_DSU_HPP
#define TOOLS_DSU_HPP

#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>

namespace tools {
  class dsu {
  private:
    // if this->m_data[x] < 0:
    //   x is a root.
    //   size(x) is -this->m_data[x].
    // if this->m_data[x] >= 0:
    //   x is an inner or leaf node.
    //   parent(x) is this->m_data[x].
    ::std::vector<int> m_data;

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

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

    explicit dsu(const int n) : m_data(n, -1) {
    }

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

      return this->m_data[x] < 0 ? x : (this->m_data[x] = this->leader(this->m_data[x]));
    }

    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) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

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

      if (this->m_data[x] > this->m_data[y]) ::std::swap(x, y);
      this->m_data[x] += this->m_data[y];
      this->m_data[y] = x;

      return x;
    }

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

      return -this->m_data[this->leader(x)];
    }

    ::std::vector<::std::vector<int>> groups() {
      ::std::vector<::std::vector<int>> res(this->size());
      for (int i = 0; i < this->size(); ++i) {
        res[this->leader(i)].push_back(i);
      }
      res.erase(::std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }
  };
}

#endif

#line 1 "tools/dsu.hpp"



#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>

namespace tools {
  class dsu {
  private:
    // if this->m_data[x] < 0:
    //   x is a root.
    //   size(x) is -this->m_data[x].
    // if this->m_data[x] >= 0:
    //   x is an inner or leaf node.
    //   parent(x) is this->m_data[x].
    ::std::vector<int> m_data;

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

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

    explicit dsu(const int n) : m_data(n, -1) {
    }

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

      return this->m_data[x] < 0 ? x : (this->m_data[x] = this->leader(this->m_data[x]));
    }

    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) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

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

      if (this->m_data[x] > this->m_data[y]) ::std::swap(x, y);
      this->m_data[x] += this->m_data[y];
      this->m_data[y] = x;

      return x;
    }

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

      return -this->m_data[this->leader(x)];
    }

    ::std::vector<::std::vector<int>> groups() {
      ::std::vector<::std::vector<int>> res(this->size());
      for (int i = 0; i < this->size(); ++i) {
        res[this->leader(i)].push_back(i);
      }
      res.erase(::std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }
  };
}