一直计划要写一篇Linux内核中关于进程调度的文章，拖欠了很久，准备动手写的时候发现了此文，看过以后觉得着实没有自己重新写的必要了，转载于此。
三月 2015
有向图强连通分支：Kosaraju’s algorithm
有向图强连通分支算是个基础算法，不过总是忘记，写下来备忘。
无向图强连通分支非常简单，使用图的遍历算法（DFS或BFS）即可，而有向图的强连通分支计算则要复杂一些，Kosaraju’s algorithm实现了\(O(n+m)\)时间复杂度的有向图强连通分支算法。
算法的核心思想在于：从有向图中任何一个点出发做DFS，必然能从图中“拖”出一个点集，和无向图中不同的是，这个点集不一定构成强连通分支，但是如果我们能通过一个合适的顺序进行DFS（“sink” vertex），则可以依次把每一个强连通分支“拖”出来，得到正确的结果，那么算法的要点则在于如何寻找这个合适的顺序。