Quiz
https://codeforces.com/contest/1144/problem/F
内容
- 無向グラフが与えられる
- それを有向グラフにし、各パスの長さを2より小さくせよ
- できない場合は-1を返す
Submit
https://codeforces.com/contest/1144/submission/52118977
観察
- 自分に矢印が向いている点からは、矢印を生やせない
- 長さ2になるため
解法
- グラフを白・黒で交互に塗る
- 任意の点からbfs
解法 satanicさん
- https://twitter.com/satanic0258/status/1112386528733347840
- 2色に塗り分けるということは二部グラフということなんだなぁ