問題リンク

実装に手間取ってしまった…

解法

まず、グラフにそもそも閉路がないならYESである。以下閉路があるとしよう。

なんでもいいので1つ閉路をとってくる。この閉路の辺のどれかを削除することが、DAGになるための必要条件である。

この閉路の長さはせいぜいであるので、どの辺を削除するかぜんぶ試して、実際にDAGになってるかを確かめよう！

計算量は

提出コード

codeforces.com

まとめ

無向グラフにしても有向グラフにしてもなんだけど、閉路検出なんか苦手