Union-find
(Mylib/DataStructure/UnionFind/unionfind.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• UnionFind(n)
• root_of(int i)
  • iのrootを得る。
• is_same(int i, int j)
  • iとjが同じ連結成分かどうかを判定する。
• merge(int i, int j)
  • iとjを同じ連結成分にし、その連結成分のrootを返す。
• size_of(int i)
  • iの属する連結成分の大きさ。
• count_group()
  • 連結成分の個数を返す。

Requirements

Notes

Problems

References

Required by

• Borůvka algorithm (Mylib/Graph/MinimumSpanningTree/boruvka.cpp)
• Kruskal algorithm (Mylib/Graph/MinimumSpanningTree/kruskal.cpp)

Verified with

• test/aoj/0575/main.test.cpp
• test/aoj/1337/main.test.cpp
• test/aoj/2955/main.test.cpp
• test/aoj/GRL_2_A/main.boruvka.test.cpp
• test/aoj/GRL_2_A/main.kruskal.test.cpp
• test/yosupo-judge/manhattanmst/main.test.cpp
• test/yosupo-judge/unionfind/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <numeric>
#include <vector>

namespace haar_lib {
  class unionfind {
    int n_, count_;
    mutable std::vector<int> parent_;
    std::vector<int> depth_, size_;

  public:
    unionfind() {}
    unionfind(int n) : n_(n), count_(n), parent_(n), depth_(n, 1), size_(n, 1) {
      std::iota(parent_.begin(), parent_.end(), 0);
    }

    int root_of(int i) const {
      if (parent_[i] == i)
        return i;
      else
        return parent_[i] = root_of(parent_[i]);
    }

    bool is_same(int i, int j) const { return root_of(i) == root_of(j); }

    int merge(int i, int j) {
      const int ri = root_of(i), rj = root_of(j);
      if (ri == rj)
        return ri;
      else {
        --count_;
        if (depth_[ri] < depth_[rj]) {
          parent_[ri] = rj;
          size_[rj] += size_[ri];
          return rj;
        } else {
          parent_[rj] = ri;
          size_[ri] += size_[rj];
          if (depth_[ri] == depth_[rj]) ++depth_[ri];
          return ri;
        }
      }
    }

    int size_of(int i) const { return size_[root_of(i)]; }

    int count_groups() const { return count_; }

    auto get_groups() const {
      std::vector<std::vector<int>> ret(n_);

      for (int i = 0; i < n_; ++i) {
        ret[root_of(i)].push_back(i);
      }

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

      return ret;
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/DataStructure/UnionFind/unionfind.cpp"
#include <algorithm>
#include <numeric>
#include <vector>

namespace haar_lib {
  class unionfind {
    int n_, count_;
    mutable std::vector<int> parent_;
    std::vector<int> depth_, size_;

  public:
    unionfind() {}
    unionfind(int n) : n_(n), count_(n), parent_(n), depth_(n, 1), size_(n, 1) {
      std::iota(parent_.begin(), parent_.end(), 0);
    }

    int root_of(int i) const {
      if (parent_[i] == i)
        return i;
      else
        return parent_[i] = root_of(parent_[i]);
    }

    bool is_same(int i, int j) const { return root_of(i) == root_of(j); }

    int merge(int i, int j) {
      const int ri = root_of(i), rj = root_of(j);
      if (ri == rj)
        return ri;
      else {
        --count_;
        if (depth_[ri] < depth_[rj]) {
          parent_[ri] = rj;
          size_[rj] += size_[ri];
          return rj;
        } else {
          parent_[rj] = ri;
          size_[ri] += size_[rj];
          if (depth_[ri] == depth_[rj]) ++depth_[ri];
          return ri;
        }
      }
    }

    int size_of(int i) const { return size_[root_of(i)]; }

    int count_groups() const { return count_; }

    auto get_groups() const {
      std::vector<std::vector<int>> ret(n_);

      for (int i = 0; i < n_; ++i) {
        ret[root_of(i)].push_back(i);
      }

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

      return ret;
    }
  };
}  // namespace haar_lib

Back to top page