コンテンツにスキップ

SamCoding Round 9 (Div. 4) F - Two-Coloured Graph

サイト
SamCoding
コンテスト
SamCoding Round 9 (Div. 4)
問題
F - Two-Coloured Graph(常設版)

nn 頂点 mm 辺の無向グラフが与えられます。多重辺はありますが、自己ループはありません。連結とは限りません。各頂点を白か黒に塗り、どの辺も両端の色が異なるようにするとき、黒い頂点の数の最小値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、0≤m≤2×1050 \le m \le 2 \times 10^5)。そのような塗り方がなければ −1-1 を出力します。

どの辺も両端の色が異なるように 2 色で塗れるのは、グラフが二部グラフのときです。二部グラフでなければ答えは −1-1 です。

二部グラフのとき、連結成分ごとに考えます。連結成分の中では、1 つの頂点の色を決めると、辺をたどって隣の頂点の色が次々に決まるので、成分全体の色も決まります。そのため、各連結成分の塗り方は、BFS や DFS で 2 色に塗り分けたものと、その白黒を入れ替えたものの 2 通りしかありません。

連結成分ごとに独立に選べるので、それぞれの成分で 2 色のうち少ないほうを黒にし、その個数を足し合わせたものが答えです。辺のない頂点だけの成分は白にすればよいので 00 個です。全体で O(n+m)O(n + m) です。

例えば入力例 1 では、成分 {1,2,3,4}\{1, 2, 3, 4\} は {1}\{1\} と {2,3,4}\{2, 3, 4\}、成分 {5,6}\{5, 6\} は {5}\{5\} と {6}\{6\} に分かれ、成分 {7}\{7\} は 00 個なので、答えは 1+1+0=21 + 1 + 0 = 2 です。

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 は各頂点の色(00 か 11)を返し、二部グラフでなければ空の配列を返します。connected_components は連結成分ごとの頂点の一覧です。成分ごとに色 00 と色 11 の個数を数え、少ないほうを足しています。

使用ライブラリ:cpp_include@4b58304