题目

现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。

给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。

例如 prerequisites[i] = [ai, bi] 表示想要学习课程 ai ，需要先完成课程 bi 。

请根据给出的总课程数 numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。

可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:输入: numCourses = 2, prerequisites = [[1,0]] 输出: [0,1]

解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 输出: [0,1,2,3] or [0,2,1,3]

解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。

因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3:输入: numCourses = 1, prerequisites = [] 输出: [0]

解释: 总共 1 门课，直接修第一门课就可。

提示:1 <= numCourses <= 2000

0 <= prerequisites.length <= numCourses * (numCourses - 1)

prerequisites[i].length == 2

0 <= ai, bi < numCourses

ai != bi

prerequisites 中不存在重复元素

注意：本题与主站 210 题相同：

解题思路分析

1、深度优先搜索；时间复杂度O(n)，空间复杂度O(n)

var res bool
var visited []int
var path []int
var edges [][]int

func findOrder(numCourses int, prerequisites [][]int) []int {
   res = true
   edges = make([][]int, numCourses) // 邻接表
   visited = make([]int, numCourses)
   path = make([]int, 0)
   for i := 0; i < len(prerequisites); i++ {
      // prev->cur
      prev := prerequisites[i][1]
      cur := prerequisites[i][0]
      edges[prev] = append(edges[prev], cur)
   }
   for i := 0; i < numCourses; i++ {
      if visited[i] == 0 {
         dfs(i)
      }
      if res == false {
         return nil
      }
   }
   for i := 0; i < len(path)/2; i++ {
      path[i], path[len(path)-1-i] = path[len(path)-1-i], path[i]
   }
   return path
}

func dfs(start int) {
   // 0 未搜索
   // 1 搜索中
   // 2 已完成
   visited[start] = 1
   for i := 0; i < len(edges[start]); i++ {
      out := edges[start][i]
      if visited[out] == 0 {
         dfs(out)
         if res == false {
            return
         }
      } else if visited[out] == 1 {
         res = false
         return
      }
   }
   visited[start] = 2
   path = append(path, start)
}

2、广度优先搜索-拓扑排序；时间复杂度O(n)，空间复杂度O(n)

func findOrder(numCourses int, prerequisites [][]int) []int {
   edges := make([][]int, numCourses)
   path := make([]int, 0)
   inEdges := make([]int, numCourses)
   for i := 0; i < len(prerequisites); i++ {
      // prev->cur
      prev := prerequisites[i][1]
      cur := prerequisites[i][0]
      edges[prev] = append(edges[prev], cur)
      inEdges[cur]++ // 入度
   }
   // 入度为0
   queue := make([]int, 0)
   for i := 0; i < numCourses; i++ {
      if inEdges[i] == 0 {
         queue = append(queue, i)
      }
   }
   for len(queue) > 0 {
      start := queue[0]
      queue = queue[1:]
      path = append(path, start)
      for i := 0; i < len(edges[start]); i++ {
         out := edges[start][i]
         inEdges[out]--
         if inEdges[out] == 0 {
            queue = append(queue, out)
         }
      }
   }
   if len(path) != numCourses {
      return nil
   }
   return path
}

总结

Medium题目，题目同leetcode 210.课程表II；类似的题目有 leetcode 207.课程表