有向グラフにトポロジカルソートが存在するための必要十分条件はどれか？ 2025.09.22 有向グラフにトポロジカルソートが存在するための必要十分条件はどれか？ グラフが有向非巡回（DAG）であること グラフが連結であること 全ての辺の重みが正であること 頂点数が辺数より多いこと トポロジカルソートは頂点を「すべての有向辺が前から後ろに向く」順序に並べる操作であり、閉路（サイクル）が存在する場合は矛盾が生じて並べられません。したがって向き付き閉路を持たない有向非巡回グラフ（DAG）であることが必要かつ十分です。連結性や重み、頂点数と辺数の大小は直接の条件ではありません。 クイズタグ: 競技プログラミング関連記事 競技プログラミングクイズ！【問題 全10問・答え付き】 | 2025年09月版
