1、前言

2、思路

使用拓扑排序的方法，拓扑排序其实是使用的 BFS 算法，简而言之使用 BFS 算法解题。算法流程如下：

• 1、统计课程安排图中每个节点的入度，生成入度表 indegrees
• 2、借助一个队列 queue，将所有入度为0的节点入队
• 3、当 queue 非空时，依次将队首节点出队，在课程安排图中删除此节点 pre：
  1⃣️ 并不是真正从邻接表中删除此节点 pre，而是将此节点对应所有邻接节点 cur 的入度 -1，即 indegrees[cur] -= 1。
  2⃣️ 当入度减1后邻接节点 cur 的入度为0，说明 cur 所有的前驱节点已经被“删除”，此时将 cur 入队
• 4、在每次 pre 出队时，执行 numCourses--
  1⃣️ 若整个课程安排图是有向无环图，则所有节点一定都入队并出队过，即完成拓扑排序。换个角
  度，若课程安排图中存在环，一定有节点的入度始终不为0.
  2⃣️ 所以，拓扑排序出队次数等于课程个数，返回 numCourses == 0 判断课程是否被成功安排。

或者使用图遍历的方法。

3、代码

拓扑排序：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];

        // 每个点对应的边
        Map<Integer, List<Integer>> adjacency = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            adjacency.put(i, new ArrayList<>());
        }

        // 二维数组，每一行有两列，即两个值，代表 cp[1] -> cp[0] 的方向
        for(int[] cp : prerequisites){
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }

        // 将入度为0的顶点加入队列
        for(int i = 0; i < numCourses; i++){
            if(indegrees[i] == 0){
                queue.offer(i);
            }
        }

        // BFS
        while(!queue.isEmpty()){
            int pre = queue.poll();
            numCourses--;
            for(int cur : adjacency.get(pre)){
                if(--indegrees[cur] == 0){
                    queue.offer(cur);
                }
            }
        }

        return numCourses == 0;
    }
}

图遍历：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graphList = new ArrayList<>();
        for(int i = 0; i < numCourses; i++){
            graphList.add(new ArrayList<>());
        }
        for(int[] pre : prerequisites){
            int from = pre[1], to = pre[0];
            graphList.get(from).add(to);
        }

        int[] visited = new int[numCourses];
        for(int i = 0; i < numCourses; i++){
            if(dfs(graphList, i, visited)){
                return false;
            }
        }
        return true;
    }

    private boolean dfs(List<List<Integer>> graphList, int course, int[] visited){
        // 正在访问中，并且又到了之前记录的访问中，说明有环
        if(visited[course] == 1){
            return true;
        }

        // 已经访问过了
        if(visited[course] == 2){
            return false;
        }

        visited[course] = 1;
        for(Integer nerberCourse : graphList.get(course)){
            if(dfs(graphList, nerberCourse, visited)){
                return true;
            }
        }
        visited[course] = 2;
        return false;
    }
}