基于染色DFS下的拓扑排序算法

拉屎的时候翻算法导论，无意停在图的DFS，然后到拓扑排序，发现这里的拓扑排序算法是基于DFS的。以前在群里还和讨论过依赖关系的算法，当时我知道的就是那个最简单的不断删除入度0顶点的算法。因为认为DFS(注：普通的DFS）算法可能需要辅助一些特殊的手段来做，不是很方便。
其实删除顶点算法并不是很好用，虽然渐近意义上是o(v+e)，实际使用中和存储结构很相关，而且不好用。然而算法导论上的基于染色的DFS算法很容易做拓扑排序：因为染色使得很容易知道回路，（灰色节点的重入代表回路）。接下来就简单了：

For each v in V do DFS
    If a child is Gray , Fail.
    If v is finished (to be black), insert v onto the font of list L.
return L.

这个算法的复杂度也是o(v+e),但是执行起来效率很高，因为删除顶点的算法需要维护“可删除性”，就是入度的维护。DFS维护一个染色信息，和顶点数相同。但是删除顶点算法可能需要临时的栈/队列来暂存计算出来的入度为0的节点。。
以前老觉得DFS多老生常谈，什么书到那都翻过去，其实发现《导论》上的染色并且维护时间戳的DFS是非常有用的。（记得以前有段时间研究GC遇到过，但是没有在意在别的上面的应用）。看来很多书还要再仔细的多翻翻。

ps，惊闻饭岛爱去世的消息，沉痛悼念！