ferinの競プロ帳

競プロについてのメモ

トポロジカルソート

トポロジカルソートとは

閉路がない有向グラフの各有向辺が順方向になるようにソートすることをトポロジカルソートと呼びます。DAG(有向無閉路グラフ)にのみ行うことができ、トポロジカルソートが行えればそのグラフはDAGであるといえます。
トポロジカルソートができる⇔DAGである
トポロジカルソート | グラフ | Aizu Online Judge

トポロジカルソートのアルゴリズム

入次数

入次数が0の頂点があれば、その頂点をソート後の結果に追加しその頂点と隣接した頂点の入次数をマイナス1する。これを入次数が0の頂点がなくなるまで繰り返すことでトポロジカルソートをすることができます。計算量はO(V+E)です。
有向非巡回グラフ(DAG)をトポロジカルソートする - マツシタケイタの技術ブログ(勉強中)


DFS

全ての点から深さ優先探索を行い、その帰りがけ順がトポロジカルソートの結果になります。計算量はO(V+E)です。
Topological sort


トポロジカルソートの通り数の数え上げ

bitDPでできます。
D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
ABC041D - ferinの競プロ帳

閉路検出

トポロジカルソートを用いて有向グラフの閉路検出をできます。トポロジカルソートができればDAGであり閉路が存在しません。逆に閉路が存在すればトポロジカルソートは不可能です。上のコードで ans.size() == v であればトポロジカルソートができた、そうでなければできなかったと判定することができます。