[LeetCode]Course Schedule

本质上就是能否topological sorting的问题，能拓扑排序的充要条件是图示DAG，也就是说没有环，我们只需要检测建的有没有环就行了，用dfs搜索如果碰到了栈上的元素就说明有环，值得注意的是图可能有多个component的要每个component都搜索到并且避免重复搜索，我们需要一个marked数组来记录，代码如下，时间复杂度O(V + E)，空间复杂度O(V + E)：


另一方面我们可以通过检测是否有SCC(strong connected components)来判断当前图是否有环。在有向图中，如果存在一系列节点，其中任意两个节点相互之间有path可以到达，那么这些节点组成一个SCC，在一个图中，可能存在多个SCC，如下图：

对于单个节点来说，自身肯定是SCC。那么对于两个和两个以上节点组成的SCC，存在环是其充要条件。首先如果有环，那么很显然环上的节点全部都是SCC；反过来的话，如果存在u，v，他们是SCC中的两个节点，那么存在从v到u的路径，并且存在从u到v的路径，这本身就形成了环。所以对于这一题，我们只需要寻找所建图是否存在size大于等于2的SCC，如果有，说明有环，不可以拓扑排序。
确定了这一点之后，我们就要考虑如何寻找SCC。我们可以使用Kosaraju's Algorithm，具体的步骤为：

1. 对图进行DFS，直到遍历完所有的节点。对于每一个节点，访问完所有相邻节点之后，把当前节点推入stack（Postorder）
2. 把原图的每一条边反过来
3. 按照stack pop出来的顺序，对于每一个节点v进行DFS，所有到达的节点就是v所在的SCC

要分析这个算法，我们首先要明确的是，如果我们把每一个SCC看做一个节点，那么所有SCC可以组成一个有向图，例如对于上图，我们可以等价为：

SCC图没有环，如果有环的话那么所有SCC节点就可以组成一个更大的SCC，这个我们的前提是矛盾的。所以第一步DFS就是相当于生成SCC图的拓扑序列，因为Postorder DFS得到序列的逆序，其实就是SCC图的拓扑排序（证明）。所有存在{ABH}的节点都比{CDE}的节点晚收录，以此类推。也就是说假设SCC1有边指向SCC2，那么SCC1里的节点都比SCC2的节点晚收录。值得注意的是，这个结论无论我们从哪个节点开始DFS都是成立的。这个顺序可以给我们带来一些好处，因为如果我们从{F}开始DFS，之后DFS {CDE}/{IJKL}, 最后访问{ABH}，那么每一个SCC之间都不会互相干扰，也就是说，我们每一次DFS得到的节点，就是当前SCC的全部节点，不会有其他SCC的节点。所以我们按照SCC图拓扑排序的逆序DFS，每一次DFS可以得到并且仅得到当前节点所在的SCC的所有节点。那么我们有两种选择，要不按照拓扑排序逆序DFS，要不把每一条边反过来，然后按照拓扑序列DFS。即使我们取反每一条边，SCC包括的节点是不会变的。这两种方法用哪一种都行，这里我们采取第二种。代码如下：

两次DFS，时间复杂度O(V + E)，空间复杂度O(V + E)。