トポロジカルソート
トポロジカルソートとは
閉路がない有向グラフの各有向辺が順方向になるようにソートすることをトポロジカルソートと呼びます。DAG(有向無閉路グラフ)にのみ行うことができ、トポロジカルソートが行えればそのグラフはDAGであるといえます。
トポロジカルソートができる⇔DAGである
トポロジカルソート | グラフ | Aizu Online Judge
トポロジカルソートのアルゴリズム
入次数
入次数が0の頂点があれば、その頂点をソート後の結果に追加しその頂点と隣接した頂点の入次数をマイナス1する。これを入次数が0の頂点がなくなるまで繰り返すことでトポロジカルソートをすることができます。計算量はO(V+E)です。
有向非巡回グラフ(DAG)をトポロジカルソートする - マツシタのお勉強メモ
トポロジカルソートした結果の数列が何通りあるか
bitDPでできます。
D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
ABC041D - ferinの競プロ帳
閉路検出
トポロジカルソートを用いて有向グラフの閉路検出をできます。トポロジカルソートができればDAGであり閉路が存在しません。逆に閉路が存在すればトポロジカルソートは不可能です。入次数のコードで ans.size() == v であればトポロジカルソートができた、そうでなければできなかったと判定することができます。
