1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| public boolean canFinish(int numCourses, int[][] prerequisites) { if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) { return true; }
int[] indegree = new int[numCourses]; for (int[] pre : prerequisites) { indegree[pre[0]]++; }
Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) { queue.offer(i); } }
while (!queue.isEmpty()) { Integer currId = queue.poll(); numCourses--; for (int[] pre : prerequisites) { if (pre[1] == currId) { indegree[pre[0]]--; if (indegree[pre[0]] == 0) { queue.offer(pre[0]); } } } }
return numCourses == 0; }
|