SamCoding Round 9 (Div. 4) F - Two-Coloured Graph
- サイト
- SamCoding
- コンテスト
- SamCoding Round 9 (Div. 4)
- 問題
- F - Two-Coloured Graph(常設版)
頂点 辺の無向グラフが与えられます。多重辺はありますが、自己ループはありません。連結とは限りません。各頂点を白か黒に塗り、どの辺も両端の色が異なるようにするとき、黒い頂点の数の最小値を求める問題です(、)。そのような塗り方がなければ を出力します。
どの辺も両端の色が異なるように 2 色で塗れるのは、グラフが二部グラフのときです。二部グラフでなければ答えは です。
二部グラフのとき、連結成分ごとに考えます。連結成分の中では、1 つの頂点の色を決めると、辺をたどって隣の頂点の色が次々に決まるので、成分全体の色も決まります。そのため、各連結成分の塗り方は、BFS や DFS で 2 色に塗り分けたものと、その白黒を入れ替えたものの 2 通りしかありません。
連結成分ごとに独立に選べるので、それぞれの成分で 2 色のうち少ないほうを黒にし、その個数を足し合わせたものが答えです。辺のない頂点だけの成分は白にすればよいので 個です。全体で です。
例えば入力例 1 では、成分 は と 、成分 は と に分かれ、成分 は 個なので、答えは です。
C++
#include "shogo-library/base/all"#include "shogo-library/graph/graph_util.hpp"#include "shogo-library/utility/container_func.hpp"
void solve() { LL(N, M); Graph<> g(N); g.read(M); auto tmp = bipartite_coloring(g); if (tmp.empty()) { print(-1); return; } auto cc = connected_components(g); ll ans = 0; for (const auto &c : cc) { al<2> cnt = {0, 0}; for (ll u : c) { cnt[tmp[u]]++; } ans += min(cnt); } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}bipartite_coloring は各頂点の色( か )を返し、二部グラフでなければ空の配列を返します。connected_components は連結成分ごとの頂点の一覧です。成分ごとに色 と色 の個数を数え、少ないほうを足しています。
使用ライブラリ:cpp_include@4b58304