二部グラフ (bipartite graph) 判定
(include/emthrm/graph/is_bipartite.hpp)

• View this file on GitHub
• Last update: 2023-02-24 21:17:22+09:00
• Include: #include "emthrm/graph/is_bipartite.hpp"

二部グラフ (bipartite graph)

• 各部分集合内の頂点間で辺が存在しないように、頂点集合を二つの部分集合に分割できるグラフである。
• 彩色数 $2$ のグラフである。
• 奇数長の閉路を含まないグラフである。

これらはすべて同値である。

時間計算量

$O(\lvert V \rvert + \lvert E \rvert)$

仕様

名前	戻り値	備考
template <typename CostType> std::vector<int> is_bipartite(const std::vector<std::vector<Edge<CostType>>>& graph);	隣接する頂点の色が同じにならないよう、無向グラフ $\mathrm{graph}$ を $2$ 色に塗り分けたときの各頂点の色。ただし二部グラフでなければ空配列を返す。	色は $0$ または $1$ で表す。

参考文献

• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，pp.93-94，マイナビ出版（2012）

Submissons

https://atcoder.jp/contests/arc099/submissions/26050245

Depends on

• 辺 (include/emthrm/graph/edge.hpp)

Verified with

• グラフ/二部グラフ判定 (test/graph/is_bipartite.test.cpp)

Code

#ifndef EMTHRM_GRAPH_IS_BIPARTITE_HPP_
#define EMTHRM_GRAPH_IS_BIPARTITE_HPP_

#include <ranges>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
std::vector<int> is_bipartite(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<int> color(n, -1);
  const auto dfs = [&graph, &color](auto dfs, const int ver, const int c)
      -> bool {
    color[ver] = c;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (color[e] == c || (color[e] == -1 && !dfs(dfs, e, c ^ 1))) {
        return false;
      }
    }
    return true;
  };
  for (int i = 0; i < n; ++i) {
    if (color[i] == -1 && !dfs(dfs, i, 0)) return std::vector<int>{};
  }
  return color;
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_IS_BIPARTITE_HPP_

#line 1 "include/emthrm/graph/is_bipartite.hpp"



#include <ranges>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 8 "include/emthrm/graph/is_bipartite.hpp"

namespace emthrm {

template <typename CostType>
std::vector<int> is_bipartite(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<int> color(n, -1);
  const auto dfs = [&graph, &color](auto dfs, const int ver, const int c)
      -> bool {
    color[ver] = c;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (color[e] == c || (color[e] == -1 && !dfs(dfs, e, c ^ 1))) {
        return false;
      }
    }
    return true;
  };
  for (int i = 0; i < n; ++i) {
    if (color[i] == -1 && !dfs(dfs, i, 0)) return std::vector<int>{};
  }
  return color;
}

}  // namespace emthrm

Back to top page