問題

問題概要

n個の頂点とm個の辺で構成されたグラフが与えられる。いくつかの辺が有向辺でいくつかの辺は無向辺である。

すべての無向辺に、グラフが循環しないように方向をつけよ。構築が不可能ならその旨を答えよ。

まず、有向辺だけで循環が発生していれば、当然構築は不可能です。

一方、有向辺だけで循環が発生していなければ必ず構築が可能です。循環が発生していないということはDAGであってトポロジカルソートが可能です。そして、無向辺についてはそのソート順に沿った方向に向きを付ければ戻ってくることはないからです。

実装的には、有向辺でトポロジカルソートしつつ、到達した頂点から生えている無向辺に適宜向きをつけていく感じでやりました。今にして考えたら、ソートするパートと向きを付けるパートは分けたほうが分かりやすかったかも・・・。