207. Course Schedule

课程选修问题，在修一些课程之前需要完成其他课程的学习，确认是否能够完成所有课程的学习。

经典的拓扑排序问题，给定一个包含n个节点的有向图 G，给出节点编号的一种排序，如果满足：
对于图G中的任意一条有向边(u, v)，u在排列中都出现在v的前面，该排列是图G的拓扑排序

• 如果图G中存在环，那么图G中不存在拓扑排序
• 如果图G是有向无环图，它的拓扑排序可能不止一种，如果图G包含任何节点却没有任何边，任意一种编号的排列都可以作为拓扑排序

将本题建模成求拓扑排序的问题

• 将每门课程看成一个节点
• 如果想学习A之前必须完成课程B，那么我们从B到A连接一条有向边，这样在拓扑排序中，B一定出现在A前面

深度优先搜索

用一个栈来存储所有已搜索完成的节点

对于一个节点u，如果它的所有相邻节点已经搜索完成，那么在搜索回溯到u的时候，u本身会变成一个搜索完成的节点。这里的相邻节点是通过u出发通过一条有向边可以到达所有节点。

假设当前搜索到了节点u，如果它的相邻节点都已经搜索完成，那么这些节点已经在栈中了，此时就可以把u入栈。此时从栈顶向栈底的顺序看，由于u处于栈顶的位置，那么u出现在所有的相邻节点的前面。因此对于u这个节点而言，是满足拓扑顺序要求的。

对图进行一次深度优先搜索。每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。

算法

对于图中的任意一个节点，它在搜索过程中有三种状态：

• 未搜索：还未搜索到这个节点
• 搜索中：搜索过这个节点，但还没有回溯到这个节点，即该节点已入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求

通过上述的三种状态，给出使用深度优先搜索得到拓扑排序的算法流程，在每一轮的搜索开始时，任取一个未搜索的节点进行深度优先搜索。

• 将当前搜索的节点u标记为搜索中，遍历该节点的每一个相邻节点v
  -- v未搜索，开始搜索v，待搜索完成回溯的u
  -- v 搜索中，找到了图中的一个环，不存在拓扑排序
  -- v 已完成，v已经在栈中，u还不在栈中，u 无论何时入栈都不会影响到 (u, v) 之间的拓扑关系，不用进行任何操作。
• 当 u 所有节点都为已完成时，将u 放入栈中，标记为已完成

在整个深度优先搜索的过程中，如果没有找到环，那么栈中存储的数据，从栈顶到栈底的顺序为拓扑排序

复杂度

• 时间复杂度：O(m + n)
• 空间复杂度：O(m + n)
• Runtime: 88 ms, faster than 95.14%
• Memory Usage: 44.3 MB, less than 50.17%

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    let index = 0
    let visited = Array(numCourses).fill(0)
    let G = Array(numCourses).fill(0).map( _ => [])
    
    for(let e of prerequisites) {
        G[e[1]].push(e[0])
    }
    
    for(let i = 0; i < numCourses ; i++) {
        if(visited[i] === 0) {
            dfs(i)
        }
    }
    
    return index === numCourses ? true : false
    
    function dfs(u) {
        visited[u] = 1
        for(let v of G[u]) {
            if(!visited[v]) {
                dfs(v)
            } else if(visited[v] === 1) {
                return false
            }
        }
        visited[u] = 2
        index++
    }
};

广度优先搜索

DFS 是一种逆向思维，最先被放入栈中的节点是在拓扑排序中最后面的节点。使用正向思维，顺序地生成拓扑排序更为直观。

拓扑排序中最前面的节点，该节点不会有任何入边，它没有任何先修课程要求，当将一个节点加入答案中后，就可以移除它的所有出边，代表它的相邻节点少了一门先修课程要求。如果某个相邻节点变成了没有任何入边的节点，代表这门课可以开始学习了。按照这样的流程，不断将没有入边的节点加入答案，直到答案中包含所有的节点或者不存在没有入边的节点(图中包含环)

算法

使用一个队列进行广度优先搜索，开始时，所有入度为0的节点都被放入队列中，它们可以作为拓扑排序最前面的节点，并且它们之间的相对顺序无关

在广度优先搜索的每一步中，取出队首的节点u：

• 将u放入答案中
• 移除 u 的所有出边，也就是将u 的所有相邻节点的入度减少1，如果某个相邻节点v的入度变为0，那么就将v放入队列中。

在广度优先搜索的过程中，如果没有找到图中的环，那么栈中存储的这所有 n 个节点，从栈顶到栈底的顺序即为一种拓扑排序。

• Runtime: 92 ms, faster than 87.03%
• Memory Usage: 43.9 MB, less than 58.45%

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    let index = 0
    let inDegree = Array(numCourses).fill(0)
    let G = Array(numCourses).fill(0).map( _ => [])
    
    for (let e of prerequisites) {
        G[e[1]].push(e[0])
        inDegree[e[0]]++
    }
    
    while(index < numCourses) {
        let hasCycle = true
        for(let i = 0; i < numCourses; i++) {
            if(inDegree[i] === 0) {
                index++
                inDegree[i] = -1
                hasCycle = false
                
                for(let w of G[i]) {
                    inDegree[w]--
                }
            }
        }
        if(hasCycle) return false
    }
    return numCourses === index ? true : false
};