F. Graph Without Long Directed Paths

Quiz

https://codeforces.com/contest/1144/problem/F

内容

  • 無向グラフが与えられる
  • それを有向グラフにし、各パスの長さを2より小さくせよ
  • できない場合は-1を返す

Submit

https://codeforces.com/contest/1144/submission/52118977

観察

  • 自分に矢印が向いている点からは、矢印を生やせない
    • 長さ2になるため

f:id:peroon:20190401034116j:plain

解法

  • グラフを白・黒で交互に塗る
  • 任意の点からbfs

解法 satanicさん