SCCでなぜpostorderを使うか

強連結成分分解（SCC）でDFSを2回するとき、なぜ1回目のDFSでpostorderを使ってその逆順をとるのかが今までしっくりきてなかった。

わざわざ逆順とかしなくても、素直にpreorderでトラバースすればいいんじゃない？と思っていた。

しかし、preorderだと上のようなグラフのときに困る。DFSをDから始めれば、(D, A, B, C)という列になるが、AからDFSを始めてしまうと、(A, B, C, D)となってしまう。こうなってしまうと、2度目の逆辺を用いたDFSでAからDに逆辺があるので、AとDが強連結だとみなされてしまう。

「トポロジカル順序でx < yならば、xの方がyよりpreorderで小さな番号が付けられるはず」と思っていたが、上のように必ずしもそうはならないようだ。

なら、postorderならどうか。postorderの場合は、
「トポロジカル順序でx < yならば、xの方が大きな番号が付けられる。」これはDFSを始める順序によらず正しそう。本当にそうか考えてみる。

今、節点vをDFSで訪れて採番しようとしている。この時点でvには、それまでにつけた番号のどれよりも大きな番号がつく。さらに、vはこれまでに訪れたいずれの節点よりもトポロジカル順序が後ではない。（もし後であればこの時点でvは採番されていないとおかしいため。）
すべての節点について上記が言えるので、トポロジカル順序が先のものほど古い番号が着くと言えそう。

あれ、ていうか今までトポロジカルソートって面倒な方法で並変えしてたけど、グラフがDAGの場合はpostorderでグラフをトラバースすればトポロジカルソート完成？
wikiに「Reverse postordering produces a topological sorting of any directed acyclic graph.」ってあったので、その認識で正しいらしい。