LeetCode207:课程表

class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { //入度表 int[] indegrees = new int[numCourses]; //课程安排图的 邻接表 List<List<Integer>> adjacency = new ArrayList<>(); Queue<Integer> queue = new LinkedList<>(); for(int i = 0; i < numCourses; i++) adjacency.add(new ArrayList<>()); // 每个课程的邻接表和入度 Get the indegree and adjacency of every course. for(int[] cp : prerequisites) { indegrees[cp[0]]++; adjacency.get(cp[1]).add(cp[0]); } // 入度为0 的课程 Get all the courses with the indegree of 0. for(int i = 0; i < numCourses; i++) if(indegrees[i] == 0) queue.add(i); // BFS TopSort. while(!queue.isEmpty()) { int pre = queue.poll(); numCourses--; for(int cur : adjacency.get(pre)) if(--indegrees[cur] == 0) queue.add(cur); } return numCourses == 0; } }