src/data-structure/disjoint-set-union.hpp

View this file on GitHub
Last update: 2023-06-20 08:00:22+09:00
Include: #include "src/data-structure/disjoint-set-union.hpp"

Depends on

src/cpp-template/header/size-alias.hpp

Verified with

test/aoj/dsl_1_a.test.cpp

Code

#pragma once

#include "src/cpp-template/header/size-alias.hpp"

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

namespace luz {

  class DisjointSetUnion {
    usize n;

    // vals[v] :=
    //   if v is root node: -1 * component size
    //   otherwise: parent node
    std::vector< isize > vals;

   public:
    DisjointSetUnion() = default;
    explicit DisjointSetUnion(usize n): n(n), vals(n, -1) {}

    usize leader(usize v) {
      if (vals[v] < 0) return v;
      return vals[v] = leader(vals[v]);
    }

    bool same(usize u, usize v) {
      return leader(u) == leader(v);
    }

    usize merge(usize u, usize v) {
      isize x = leader(u);
      isize y = leader(v);
      if (x == y) return x;

      if (-vals[x] < -vals[y]) std::swap(x, y);

      vals[x] += vals[y];
      vals[y] = x;
      return x;
    }

    usize group_size(usize v) {
      return -vals[leader(v)];
    }
  };

} // namespace luz

#line 2 "src/data-structure/disjoint-set-union.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

}
#line 4 "src/data-structure/disjoint-set-union.hpp"

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

namespace luz {

  class DisjointSetUnion {
    usize n;

    // vals[v] :=
    //   if v is root node: -1 * component size
    //   otherwise: parent node
    std::vector< isize > vals;

   public:
    DisjointSetUnion() = default;
    explicit DisjointSetUnion(usize n): n(n), vals(n, -1) {}

    usize leader(usize v) {
      if (vals[v] < 0) return v;
      return vals[v] = leader(vals[v]);
    }

    bool same(usize u, usize v) {
      return leader(u) == leader(v);
    }

    usize merge(usize u, usize v) {
      isize x = leader(u);
      isize y = leader(v);
      if (x == y) return x;

      if (-vals[x] < -vals[y]) std::swap(x, y);

      vals[x] += vals[y];
      vals[y] = x;
      return x;
    }

    usize group_size(usize v) {
      return -vals[leader(v)];
    }
  };

} // namespace luz