ARC111-D Orientation
色々実験して性質を観察するの大事・・・
問題
解法
とりあえず頂点数が小さい範囲でどのような向き付けができるかを見てみる.
すると任意の2頂点u,vに対して
u→vの向きづけがあるならば,c[u]>=c[v]
が成り立っていることがわかる.
あとは,各頂点からDFSをしてやって,まだ向きが決まっていない辺に対してc[i]>=c[j]なるところに向きをつけてやる.このとき,i→jの向き付が決まるとjから出ている残りの辺の向きも決まることに注意する.(サイクルであるかパスであるか)