210. Course Schedule II

课程选修问题，在修一些课程之前需要完成其他课程的学习，如果按照先决条件，可以完成所有课程的学习，返回可能的学习顺序。如果不能完成所有课程的学习，返回空数组。

图的两种表示方法：邻接矩阵与邻接表。

输入： 需要完成的课程数
输出：先决条件数组，[[3,1],[3,2]] 比如在完成课程 3 之前必须先完成课程 1 和 课程 2

• 时间复杂度： O(m + n)，n 为课程数，m 为先修课程要求数，为对图进行 dfs 或 bfs 的时间复杂度
• 空间复杂度：O(m + n)，对图进行搜索，需要存储成邻接表的形式，空间复杂度为 O(m + n)， bfs 需要最多 O(n) 的队列空间进行迭代，还需要几个O(n)空间存储 节点入度，最终答案。

BFS

思路：将先决条件转换成邻接表，将入度为0的课程依次入队，开始BFS，然后将后学的课程入度减1，再将入度为0的课程入队进行学习，直到所有课程学完为止。

• Runtime: 100 ms, faster than 69.62%
• Memory Usage: 44 MB, less than 58.45%

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
  const inDegress = Array(numCourses).fill(0)
  const res = []
  const G = Array(numCourses).fill(0).map(_ => [])
  
  for(let e of prerequisites) {
    G[e[1]].push(e[0])
    inDegress[e[0]]++
  }
  
  while(res.length < numCourses) {
    let hasCycle = true
    for (let i = 0; i < numCourses; i++) {
      if(inDegress[i] === 0) {
        res.push(i)
        inDegress[i] = -1
        hasCycle = false
        
        for(let w of G[i]) {
          inDegress[w]--
        }
      }
    }
    if(hasCycle) return []
  }
  return res
};

DFS

• Runtime: 96 ms, faster than 81.22%
• Memory Usage: 44.6 MB, less than 37.69%

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */

var findOrder = function(numCourses, prerequisites) {
    let stack = []
    let visited = Array(numCourses).fill(0)
    let hasCycle = false
    let G = Array(numCourses).fill(0).map(_ => [])
    
    for(let e of prerequisites) {
        G[e[1]].push(e[0])
    }
    for (let i = 0; i < numCourses && !hasCycle; i++) {
        if(!visited[i]) {
            dfs(i)
        }
        if(hasCycle) return []
    }
    return stack.reverse()
    
    
    function dfs(u) {
        visited[u] = 1
        for(let w of G[u]) {
            if(visited[w] === 0) {
                dfs(w)
                if(hasCycle) return
            } else if(visited[w] === 1){
                hasCycle = true
                return
            }
        }
        visited[u] = 2
        stack.push(u)
    }
};