E. Cover it!

Quiz

AC

解法

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

参考

私の誤解法

  • (白で最小点被覆を貪欲にやろうとして・・・↓)
  • 次数多い点から取り出して、まだ塗られていないなら白で塗り、その隣は塗られていなければ黒で塗る
  • 白を答えとして出力する
  • ダメな例

f:id:peroon:20190610222012j:plain

別解

f:id:peroon:20210122045250p:plain