题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [207. 课程表 - 图1,207. 课程表 - 图2] ，表示如果要学习课程 则 必须 先学习课程 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

  • 1 <= numCourses <= 105
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

    方案（拓扑排序）

    ```go type IntSet map[int]bool

func (s IntSet) Add(n int) { s[n] = true }

func (s IntSet) Has(n int) bool { _, ok := s[n] return ok }

func (s IntSet) Delete(n int) { delete(s, n) }

func (s IntSet) Empty() bool { return len(s) == 0 }

func canFinish(numCourses int, prerequisites [][]int) bool { // 转化成图中是否有环的问题 adj := map[int]IntSet{} revAdj := map[int]IntSet{} for i := 0; i < numCourses; i++ { adj[i] = IntSet{} revAdj[i] = IntSet{} }

  1. for _, pre := range prerequisites {
  2.     adj[pre[0]].Add(pre[1])
  3.     revAdj[pre[1]].Add(pre[0])
  4. }
  6. // 下一批可以移除的点
  7. canRemove := []int{}
  8. for k, v := range adj {
  9.     if v.Empty() {
  10.         canRemove = append(canRemove, k)
  11.     }
  12. }
  14. for len(canRemove) > 0 {
  15.     length := len(canRemove)
  16.     for i := 0; i < length; i++ {
  17.         node := canRemove[0]
  18.         canRemove = canRemove[1:]
  19.         delete(adj, node)
  20.         for pointerNode := range revAdj[node] {
  21.             adj[pointerNode].Delete(node)
  22.             if adj[pointerNode].Empty() {
  23.                 canRemove = append(canRemove, pointerNode)
  24.             }
  25.         }
  26.     }
  27. }
  29. return len(adj) == 0

} ```

原文

https://leetcode-cn.com/problems/course-schedule/