二部グラフ判定
(graph/bipartite/bipartite_check.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/bipartite/bipartite_check.hpp"

概要

二部グラフの判定.

計算量

$O(E + V)$

使用例

• is_bipartite(g) : 二部グラフの判定.
  • 片方の集合の大きさが欲しかったら, 適宜コメントを外す.

Code

/**
 * @brief 二部グラフ判定
 * @docs docs/graph/bipartite/bipartite_check.md
 */

template <typename T>
// int is_bipartite(const Graph<T> &g) {
bool is_bipartite(const Graph<T> &g) {
    bool isbi = true;
    vector<int> color(g.V, 0);
    auto dfs = [&](auto &&f, int i, int clr) -> void {
        if (color[i] != 0) return;
        color[i] = clr;
        for (auto &e : g.mat[i]) {
            if (color[e.to] == 0)
                f(f, e.to, -clr);
            else if (color[e.to] == clr)
                isbi = false;
        }
    };
    dfs(dfs, 0, 1);
    return isbi;
    // int cnt = 0;
    // for (auto &e : color)
    //     if (e == 1) ++cnt;
    // return isbi ? -1 : cnt;
}

#line 1 "graph/bipartite/bipartite_check.hpp"
/**
 * @brief 二部グラフ判定
 * @docs docs/graph/bipartite/bipartite_check.md
 */

template <typename T>
// int is_bipartite(const Graph<T> &g) {
bool is_bipartite(const Graph<T> &g) {
    bool isbi = true;
    vector<int> color(g.V, 0);
    auto dfs = [&](auto &&f, int i, int clr) -> void {
        if (color[i] != 0) return;
        color[i] = clr;
        for (auto &e : g.mat[i]) {
            if (color[e.to] == 0)
                f(f, e.to, -clr);
            else if (color[e.to] == clr)
                isbi = false;
        }
    };
    dfs(dfs, 0, 1);
    return isbi;
    // int cnt = 0;
    // for (auto &e : color)
    //     if (e == 1) ++cnt;
    // return isbi ? -1 : cnt;
}

Back to top page