Codeforces Round #565 (Div. 3) Problem E. Cover it!

問題概要

n 頂点 m の単純連結グラフ(自己ループ, 多重辺なし)が与えられる. n 個の頂点から最大でも \lfloor n/2 \rfloor 個までの頂点を選び, すべての頂点が a. 選択済み, b. 自分の隣接頂点が選択されている のいずれかの状態になるようにしたい. どのようにえらべばよいか？

問題へのリンク

 制約

  • 2 \le n \le 2\times 10^5
  • n-1 \le m \le min(2\times 10^5, n(n-1)/2)
  • グラフは単純かつ連結

解説

もしグラフが二部グラフなら, 赤の頂点と白の頂点の少ない方をすべて塗れば条件を満たせるのはすぐわかります. 問題は与えられるグラフが二部グラフとは限らない点ですが, 適切に辺を削除すれば二部グラフにできるでしょうか？

これは, 木が二部グラフだったことを思い出せば, グラフが木になるまで辺を削除していくことにより達成できます. ただし, 実装上は非連結なら辺を追加していくことを繰り返していきます(クラスカル法と同じです).

あとは bfs なり dfs で木の各頂点を塗り, 数が少ない色の頂点をすべて出力すれば終わりです.

実装

木の構築は Union-Find でやっています. また木の頂点の色を 0/1 でぬっているので, 色の配列の総和が 1 で塗った頂点の個数になる事実を利用しています.

Submission #145013976 - Codeforces