トポロジカルソートのやり方
毎回毎回調べるのあほみたいじゃないですか
前提
キュー、もしくはその上位互換(Dequeなど)が扱える必要があります
JavaScriptなどには標準でキューが用意されていないので自力で用意してください、そんなにむずくはない やること
各頂点について、入次数をメモ
キューを用意して、入次数0の頂点を入れておく
キューが空になるまで、以下を繰り返す
キューの先頭を取り出す
取り出した頂点をトポロジカルソートの次の頂点として採用
取り出した頂点をグラフから削除
取り出した頂点から出ている辺が刺さっている先の入次数を1減らせばいい
新たに入次数が0になった場所があれば、それをキューに入れる
補足
計算量は$ O(|V| + |E|)です
BFSなのでそりゃそう
トポロジカルソートした結果の長さがもとのグラフの頂点数と一致しない場合、そいつはDAGじゃない
DFSの帰りがけ順に注目するトポロジカルソートのやり方もあるが、これだとDAG判定がちょっとだるい