一、题目描述

你这个学期必须选修 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] 中的所有课程对 互不相同

二、思路讲解

        这是一道经典的拓扑排序问题，课程能不能修完 == 有向图中是否存在环，有向图中，一个节点的入度为他的先修课程。

        2.1 方法一：广度优先搜索bfs

        思路如下：通过bfs进行拓扑排序。利用一个队列，将入度数为0的节点加入到队列中（这些课程没有先修课程，可以访问），然后将队列中的节点依次出队，每出队一个节点，就相当于访问了这个节点（修了这门课程），就要将它在有向图中“删除”，即将它所有的出度的入度数都-1，然后将这时可能有些课程的入度数为0了，那这也是可以修的课程，也将他放入队列中。当队列为空时，拓扑排序完成，如果所有节点都访问到了，说明有向图中没有环；反之，有环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //记录入度数
        int []indegrees = new int[numCourses];
        //出度表
        List<List<Integer>> edegree = new ArrayList<>();
        for(int i=0; i<numCourses; i++) {
            edegree.add(new ArrayList<Integer>());
        }

        //统计每个节点的出度节点  和  入度数
        for(int i=0; i<prerequisites.length; i++) {
            edegree.get(prerequisites[i][1]).add(prerequisites[i][0]);
            indegrees[prerequisites[i][0]]++;
        }

        //bfs
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0; i<numCourses; i++) {
            if(indegrees[i] == 0) {
                queue.add(i);
            }
        }
        int visited = 0;    //访问节点的数量，如果和节点总数一致，说明每个节点都访问到了，有向图中不存在环
        while(!queue.isEmpty()) {
            visited++;
            int node = queue.poll();
            //把该节点的所有出度的入度数都-1，相当于把这个节点从有向图中删除
            for(int ede : edegree.get(node)) {
                indegrees[ede]--;
                //把入度数为0的节点放到队列中，这些节点是可以访问的
                if(indegrees[ede] == 0) {
                    queue.add(ede);
                }
            }
        }
        return visited==numCourses;
    }
}

        时间复杂度：        O(M + N)         M为课程数，N为先修课程的要求数

        空间复杂度：        O(M + N)

        2.2 深度优先搜索dfs

        跟bfs从入度思考相比，dfs从出度思考，更像是一种逆向思维。

        思路：深度遍历判断有向图是否存在环。用visit数组记录节点的访问状态（1：当前节点正在访问； 0：未被访问； -1：被其他节点访问过）。如果当前节点的状态为-1，说明已经被其他节点访问过，已经被从有向图中“删除了”，无需考虑；而状态为1，说明是正在被访问的，则说明走了回头路，即存在环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //记录每个节点的访问情况    1：当前节点正在访问； 0：未被访问； -1：被其他节点访问过
        int []visit = new int[numCourses];
        //出度表
        List<List<Integer>> edegree = new ArrayList<>();
        for(int i=0; i<numCourses; i++) {
            edegree.add(new ArrayList<Integer>());
        }

        //统计每个节点的出度节点
        for(int i=0; i<prerequisites.length; i++) {
            edegree.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }

        for(int i=0; i<numCourses; i++) {
            if(!dfs(edegree, visit, i)) {
                return false;
            }
        }
        return true;
    }

    boolean dfs(List<List<Integer>> edegree, int []visit, int i) {
        //如果已经被其他节点访问过，说明不需要再访问了
        if(visit[i] == -1) {
            return true;
        }
        //正在被当前节点访问，说明走了回头路，即存在环
        if(visit[i] == 1) {
            return false;
        }
        visit[i] = 1;
        //向下访问，每个出度都要走到
        for(int ede : edegree.get(i)) {
            if(!dfs(edegree, visit, ede)) {
                return false;
            }
        }
        visit[i] = -1;
        return true;
    }
}

        可以把邻接表和访问状态数组设置为公共变量，减少递归传参对性能的损耗： 

class Solution {

    int []visit;
    List<List<Integer>> edegree;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visit = new int[numCourses];
        edegree = new ArrayList<>();
        for(int i=0; i<numCourses; i++) {
            edegree.add(new ArrayList<Integer>());
        }

        //统计每个节点的出度节点
        for(int i=0; i<prerequisites.length; i++) {
            edegree.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }

        for(int i=0; i<numCourses; i++) {
            if(!dfs(i)) {
                return false;
            }
        }
        return true;
    }

    boolean dfs(int i) {
        if(visit[i] == -1) {
            return true;
        }
        if(visit[i] == 1) {
            return false;
        }
        visit[i] = 1;
        for(int ede : edegree.get(i)) {
            if(!dfs(ede)) {
                return false;
            }
        }
        visit[i] = -1;
        return true;
    }
}

        时间复杂度：        O(M + N)         M为课程数，N为先修课程的要求数

        空间复杂度：        O(M + N)