LeetCode/207. 课程表

207. 课程表

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse - 1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例1 ：

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例2：

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

提示:

1. 输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
2. 你可以假定输入的先决条件中没有重复的边。
3. 1 <= numCourses <= 10^5

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

一看到这种题目，就知道是有向图的拓扑排序，而拓扑排序的思路和广度优先搜索遍历大同小异。

具体代码如下：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new ArrayList<>());
        }

        //遍历数组，建立有向图结构，初始化各节点入度
        for (int[] prerequisite : prerequisites) {
            int u = prerequisite[0];
            int v = prerequisite[1];

            inDegree[u]++;

            graph.get(v).add(u);
        }

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

        //广度优先搜索遍历
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            if (graph.get(temp) == null)
                continue;
            ArrayList<Integer> list = graph.get(temp);
            for (Integer integer : list) {
                if (--inDegree[integer] == 0) {
                    queue.add(integer);
                }
            }
        }

        //查看是否存在环
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] != 0)
                return false;
        }
        return true;
    }
}