There are a total of n courses you have to take, labeled from 0 to n-1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?Example 1:Input: 2, [[1,0]] Output: trueExplanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.Example 2:Input: 2, [[1,0],[0,1]]Output: falseExplanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.Note:The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.You may assume that there are no duplicate edges in the input prerequisites.难道: medium题目:课程编号为0到n-1的n门课程需要我们去学习。学习某些课程需要先学习其预备课程，例如学习课程0就要先学习课程1, 用如下形式表示这种关系[0, 1].给定全部课程数，以及这种课程与课程之前的关系，是否可以完成全部课程学习？注意：前置课程是由一些边组成的图不是毗邻的矩阵。你可以假定前置课程这种关系表示没有重复的输入。思路：BFS, DFS拓扑图遍历1.找出一个出度为0的结点。2.移除该出度为0结点的所有边，然后执行1.BFSRuntime: 6 ms, faster than 91.38% of Java online submissions for Course Schedule.class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // (Array -> List) to store graph List<Integer>[] nodes = new ArrayList[numCourses]; for (int i = 0; i < numCourses; i++) { nodes[i] = new ArrayList<Integer>(); } // count in degree int[] inDegree = new int[numCourses]; for (int i = 0; i < prerequisites.length; i++) { (nodes[prerequisites[i][0]]).add(prerequisites[i][1]); inDegree[prerequisites[i][1]] += 1; } // count zero in degree int zeroInDegreeCount = 0; Queue<Integer> zeroInDegreeQueue = new LinkedList<>(); for (int i = 0; i < inDegree.length; i++) { if (inDegree[i] <= 0) { zeroInDegreeQueue.add(i); zeroInDegreeCount++; } } // bfs while (!zeroInDegreeQueue.isEmpty()) { for (Integer i : nodes[zeroInDegreeQueue.poll()]) { if (–inDegree[i] <= 0) { zeroInDegreeQueue.add(i); zeroInDegreeCount++; } } } return zeroInDegreeCount == numCourses; }}DFSRuntime: 51 ms, faster than 19.25% of Java online submissions for Course Schedule.class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<Integer>[] nodes = new ArrayList[numCourses]; for (int i = 0; i < numCourses; i++) { nodes[i] = new ArrayList<Integer>(); } for (int i = 0; i < prerequisites.length; i++) { (nodes[prerequisites[i][0]]).add(prerequisites[i][1]); } boolean[] visited = new boolean[numCourses]; for (int i = 0; i < numCourses; i++) { boolean hasCircle = dfs(i, visited, nodes); if (hasCircle) { return false; } } return true; } // function to verify if circle exist private boolean dfs(int c, boolean[] visited, List<Integer>[] nodes) { boolean hasCircle = false; visited[c] = true; List<Integer> lst = nodes[c]; for (int i = 0; i < lst.size(); i++) { if (visited[lst.get(i).intValue()]) { return true; } hasCircle = dfs(lst.get(i), visited, nodes); } visited[c] = false; return hasCircle; }}