题目：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [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] 中的所有课程对 互不相同

    解法1：拓扑排序+广度优先搜索，时间复杂度o(m+n)，空间复杂度o(m+n)

  1. 给定一个包含 nn 个节点的有向图G，我们给出它的节点编号的一种排列，如果满足：对于图 G 中的任意一条有向边 (u, v)，u 在排列中都出现在v的前面。那么称该排列是图 G 的「拓扑排序」
    1. 如果图G中存在环，则G不存在拓扑排序
    2. 如果图G是有向无环图，则拓扑排序不止一种
    3. 本题可约化为： 课程安排图是否是 有向无环图(DAG)。即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。
    4. 通过课程前置条件列表prerequisites可以得到课程安排图的邻接表adjacency，以降低算法时间复杂度，以下两种方法都会用到邻接表。
  2. 我们将每一门课看成一个节点；如果想要学习课程 A 之前必须完成课程 B，那么我们从 B 到 A 连接一条有向边。这样以来，在拓扑排序中，B 一定出现在 A 的前面。
  3. 统计课程安排图中每个节点的入度，生成 入度表 indegrees，下标是课程，元素值代表入度。借助一个队列 queue，将所有入度为 0 的节点入队。
  4. 当 queue 非空时，依次将队首节点出队，在课程安排图中删除此节点 pre，每次删除的即为没有前驱的结点：
  5. 并不是从邻接表中删除此节点 pre，而是将此节点对应所有邻接节点 cur 的入度 −1，即 indegrees[cur] -= 1;
  6. 当入度 −1后邻接节点 cur 的入度为 0，说明 cur 所有的前驱节点已经被 “删除”，此时将 cur 入队。
  7. 在每次 pre 出队时，执行 numCourses—；
  8. 若整个课程安排图是有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序。换个角度说，若课程安排图中存在环，一定有节点的入度始终不为 0。

  9. 因此，拓扑排序出队次数等于课程个数，返回 numCourses == 0 判断课程是否可以成功安排。 ```java class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) {

    1.  if(numCourses <= 0)
    2.      return false;
    3.  // 入度表    
    4.  int []inDegree = new int[numCourses];
    5.  // 邻接表
    6.  List<List<Integer>> adjacency = new ArrayList<>();
    7.  for(int i = 0; i < numCourses ; i++){
    8.      adjacency.add(new ArrayList<>());
    9.  }
    10.  // 队列，用于删除没有前驱的结点
    11.  Deque<Integer> deque = new LinkedList<>();
    12.  // 初始化邻接表和入度表
    13.  for(int []cp : prerequisites){
    14.      inDegree[cp[0]]++;
    15.      // cp[1]为cp[0]的先导课程，因此定义映射关系 cp[1] -> cp[0]
    16.      adjacency.get(cp[1]).add(cp[0]);
    17.  }
    19.  // 把入度表为0的元素先入队，下标代表那个元素
    20.  for(int i = 0 ; i < numCourses ;i++){
    21.      if(inDegree[i] == 0)
    22.          deque.add(i);
    23.  }
    24.  // 前驱节点
    25.  int pre = 0;
    26.  while(!deque.isEmpty()){
    27.      // 每次队头认为是没有前驱的节点
    28.      pre = deque.poll();
    29.      numCourses--;
    30.      // 找到邻接节点
    31.      for(int cur : adjacency.get(pre)){
    32.          // 入度表对应入度减1，如果入度为0，则又入队
    33.          if(--inDegree[cur] == 0){
    34.              deque.add(cur);
    35.          }
    36.      }
    38.  }
    39.  // 最终如果课程数不为0，说明有环
    40.  return numCourses == 0;

    }

}

<a name="XR6U9"></a>
## 解法2：拓扑排序+深度优先搜索，时间复杂度o(m+n)，空间复杂度o(m+n)

1. 借助邻接表和备忘录完成，备忘录中保存着当前节点的状态，邻接表中保存当前节点可以到达的邻居结点
1. 备忘录isVsited[i]有如下状态：
   1. -1：当前节点被其他节点访问过
   1. 0：当前节点未被访问
   1. 1：正在访问当前节点
3. 在访问当前节点时候isVisited[i] = 1；访问完成后，isVisted[i] = -1，进行回溯；
3. 如果让有向图不成环，则最终isVisted[i]中的任意节点状态都应该是-1，如果有1的情况说明有的节点只能在自己的dfs中访问到自己，而无法让别人访问，最终成环。
3. 如果dfs成环返回false，否则最后返回true。
```java
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses <= 0)
            return false;
        // 备忘录    
        int []isVisited = new int[numCourses];
        // 邻接表
        List<List<Integer>> adjacency = new ArrayList<>();
        for(int i = 0; i < numCourses ; i++){
            adjacency.add(new ArrayList<>());
        }

        // 初始化邻接表
        for(int []cp : prerequisites){
            // cp[1]为cp[0]的先导课程，因此定义映射关系
            adjacency.get(cp[0]).add(cp[1]);
        }

        // 开始从每个节点遍历
        for(int i = 0 ; i < numCourses ; i++){
            if(!dfs(isVisited,adjacency,i))
                return false;
        }
        return true;
    }

    public boolean dfs(int []isVisited,List<List<Integer>> adjacency,int cur){
        // -1说明每个节点都能够被其他节点访问到，不会出现环
        if(isVisited[cur] == -1)
            return true;
        // 如果最后有1，说明有的节点只能被自己访问到
        if(isVisited[cur] == 1)
            return false;
        // 开始访问当前节点
        isVisited[cur] = 1;
        // dfs遍历邻接结点
        for(Integer next : adjacency.get(cur)){
            if(!dfs(isVisited,adjacency,next))
                return false;
        }
        isVisited[cur] = -1;
        return true;
    }

}