Educational Codeforces Round 36 - D. Almost Acyclic Graph
実装に手間取ってしまった…
解法
まず、グラフにそもそも閉路がないならYES
である。以下閉路があるとしよう。
なんでもいいので1つ閉路をとってくる。この閉路の辺のどれかを削除することが、DAGになるための必要条件である。
この閉路の長さはせいぜいであるので、どの辺を削除するかぜんぶ試して、実際にDAGになってるかを確かめよう!
計算量は
提出コード
まとめ
無向グラフにしても有向グラフにしてもなんだけど、閉路検出なんか苦手