二部グラフのライブラリ
二部グラフのライブラリです。
この問題で $verify$ しています。
$DFS$ を実装するだけですが、持っておくと便利な時がたまにあります。
二部グラフかどうかを判定したい無向グラフの隣接リストg
を投げて使います。二部グラフではない場合は、-1
が返ってきて、二部グラフである場合は、色を塗った時の片方の色の個数が返ってきます。
int BipartiteGraph(const vector<vector<int>> &g) { int n = g.size(); vector<int> color(n, -1); int white_cnt = 0; function<bool (int, int, int)> dfs = [&](int u, int prev, int c) { color[u] = c; if (c == 1) white_cnt ++; for (auto v : g[u]) if (v != prev) { if (color[v] == -1) { if (!dfs(v, u, 1 - c)) return false; } else if (color[v] != 1 - c) { return false; } } return true; }; if (!dfs(0, -1, 0)) return -1; return white_cnt; }