有向グラフの頂点を、すべての辺が前から後ろへ向かうように一列に並べるトポロジカルソートが可能であるための条件はどれか。

解説

正解は「グラフに有向閉路がない」です。トポロジカルソートは、作業の前後関係のような「A は B より前」という制約を有向辺で表したとき、すべての制約を満たす順序を求めるものです。有向閉路があると、閉路上の各頂点を他の頂点より前に置く必要が生じて矛盾するため、並べられません。有向閉路のないグラフ（DAG）なら必ず並べられ、入次数0の頂点から順に取り除く方法などで $O(V+E)$ で求められます。「グラフが強連結である」と、2頂点以上なら必ず有向閉路があるため並べられません。「すべての頂点の入次数が等しい」ことは条件ではありません。「辺の重みがすべて正である」ことは、重みを使わないトポロジカルソートには関係ありません。