d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 問題 https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A 有向グラフ上の閉路を求める問題 制約 考え方 与えられた有向グラフを とする。 に閉路が存在する場合は与えられた有向グラフは ではない。ここで トポロジカルソートが可能 のテクニックが利用できる。すなわち、 が であればトポロジカルソートが可能で、トポロジカルソート後の頂点数 元の頂点数 となる。 Aizu Online Judge 別解 今回の場合は制約が小さいので、各有向辺 のコストを としてベルマンフォード法の負の閉路検出方法でも解を求めることができる。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F12%2F15%2F150702" title="GRL_4_A：有向グラフの閉路検査 - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-12-15 15:07:02 rich https://tutuz.hateblo.jp/entry/2018/12/15/150702 1.0 100%