GRL_4_A：有向グラフの閉路検査
問題
https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A
有向グラフ上の閉路を求める問題
制約
考え方
与えられた有向グラフを とする。
に閉路が存在する場合は与えられた有向グラフは
ではない。ここで
トポロジカルソートが可能
のテクニックが利用できる。すなわち、 が
であればトポロジカルソートが可能で、トポロジカルソート後の頂点数
元の頂点数 となる。
別解
今回の場合は制約が小さいので、各有向辺 のコストを
としてベルマンフォード法の負の閉路検出方法でも解を求めることができる。閉路が存在する場合は
のコストが効いて
回目のループでも頂点のコストが更新されるためである。
どこに着目して考察するべきだったか
トポロジカルソート可能
何がバグっていたか
得た知見
トポロジカルソート可能