E. Cover it!

Quiz

https://codeforces.com/contest/1176/problem/E

ACコード

https://codeforces.com/contest/1176/submission/55399046

解法

  • グラフを2色に塗る(例えば白と黒とする)
  • 現在見ているノードを白で塗ったなら、隣はできるだけ黒で塗るようにする
  • 塗り終わった時、数の少ない色の方を答えとして出力

参考

私の誤解法

  • 次数多い点から取り出して、まだ塗られていないなら白で塗り、その隣は塗られていなければ黒で塗る
  • 白を答えとして出力する
  • ダメな例

f:id:peroon:20190610222012j:plain