トポロジカルソート
DAGの各頂点を、すべての有向辺が順方向になるように並べ替えること。 あるグラフがDAGであることとトポロジカルソートできることは同値。閉路検出などにも使える。 計算量:$ O(|V|+|E|)
幅優先探索(BFS)でのアルゴリズム:
1. すべての頂点に対して、入ってくる辺の数(入次数)を数えておく
2. 次数が0の頂点をキューに入れる
3. キューの要素数が0になるまで以下のように幅優先探索をする
1. キューから取り出した次数が0の点をトポロジカルソートした時の次の頂点として採用し、その頂点をグラフから削除する
2.新たに次数が0になったところをキューに入れる
実装上はグラフから削除するのではなく、探索済み頂点リストと入次数カウントリストを用意して、それらを更新していく。
ソート結果は一意とは限らない。
辞書順最小にしたい場合はキューをheapqにする。
あり得るソート結果が何通りかはbitDPで求められる。