Check bipartite graph (Using union-find)
(Mylib/Graph/BipartiteGraph/construct_bipartite_graph.cpp)

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

Operations

Requirements

Notes

Problems

• CODE FESTIVAL 2017 qual B C - 3 Steps
• ARC 036 D - 偶数メートル

References

Code

#pragma once

namespace haar_lib {
  template <typename UF>
  class bipartite_graph : public UF {
    int n_;

    using super = UF;

  public:
    bipartite_graph() {}
    bipartite_graph(int n) : super(2 * n), n_(n) {}

    void add_diff(int i, int j) {  // iとjを異なる色で塗る。
      super::merge(i, j + n_);
      super::merge(i + n_, j);
    }

    void add_same(int i, int j) {  // iとjを同じ色で塗る。 = iとjを同じ頂点と見做す。
      super::merge(i, j);
      super::merge(i + n_, j + n_);
    }

    bool is_bipartite_graph(int i) {  // iを含む連結グラフが二部グラフかを判定する。
      return not super::is_same(i, i + n_);
    }

    bool is_same(int i, int j) {  // iとjが同じ色で塗られているか判定する。
      return super::is_same(i, j);
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Graph/BipartiteGraph/construct_bipartite_graph.cpp"

namespace haar_lib {
  template <typename UF>
  class bipartite_graph : public UF {
    int n_;

    using super = UF;

  public:
    bipartite_graph() {}
    bipartite_graph(int n) : super(2 * n), n_(n) {}

    void add_diff(int i, int j) {  // iとjを異なる色で塗る。
      super::merge(i, j + n_);
      super::merge(i + n_, j);
    }

    void add_same(int i, int j) {  // iとjを同じ色で塗る。 = iとjを同じ頂点と見做す。
      super::merge(i, j);
      super::merge(i + n_, j + n_);
    }

    bool is_bipartite_graph(int i) {  // iを含む連結グラフが二部グラフかを判定する。
      return not super::is_same(i, i + n_);
    }

    bool is_same(int i, int j) {  // iとjが同じ色で塗られているか判定する。
      return super::is_same(i, j);
    }
  };
}  // namespace haar_lib

Back to top page