私たちは、グラフアルゴリズムとして DFS や BFS を学ぶと 頂点 s から頂点 t へ辿り着けるかどうかを判定する 連結成分の個数を求める 二部グラフ判定する トポロジカルソートする などといった例題を次々とこなしていき、グラフ探索スキルを高めていく道を歩んでいくことになります。そんな長い道のりにおいて、脱初級者の登竜門とも言うべき難所として、本記事ではサイクル検出を解説します! AtCoder でも、ABC-E や水色 diff などでよく出題されるテーマです。 目次 最終的なサイクル検出コードを「4. まとめのコード」で示すので、時間のない方はそこに飛んでもらえたらと思います。Yosupo Judge Library Checker の「Cycle Detection (Directed)」と「Cycle Detection (Undirected)」を通します。 また、ABC