题目你这个学期必须选修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 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i]中的所有课程对互不相同题解class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { int[] inDgree new int[numCourses];//存每门课的入度数 ListListInteger adjList new ArrayList();//存前置-后置 for(int i 0;i numCourses;i){ adjList.add(new ArrayList()); } for(int[] prerequisite : prerequisites){ int course prerequisite[0]; int preCourse prerequisite[1]; inDgree[course]; //adjList.get(x).add(y)往 x 对应的子列表追加 y adjList.get(preCourse).add(course); } QueueInteger queue new LinkedList(); for(int i 0;i numCourses;i){ if(inDgree[i] 0){ queue.offer(i); } } int count 0; while(!queue.isEmpty()){ int selectedCourse queue.poll(); count; ListInteger nextCourses adjList.get(selectedCourse); for(int nextCourse : nextCourses){ inDgree[nextCourse]--; if(inDgree[nextCourse] 0){ queue.offer(nextCourse); } } } return count numCourses;//环内节点入度永远不为 0导致count偏小 } }思路思路不断挑选当前没有前置条件入度 0的节点。构建图邻接表记录每一个节点入度将入度等于 0 节点送入队列循环取出节点消除该节点向外发出的边邻居入度 -1。邻居入度归零加入队列。统计一共取出多少节点。取出节点总数 全部节点无环 课程可以全部学完取出数量 总节点存在环路环内节点入度永远不为 0无法被选出来。返回 false