There are numCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates you must take course b before course a.
Return true if you can finish all courses (no cycle), false otherwise.
Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Take 0 then 1.
Example 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Cycle: 0→1→0.
1 <= numCourses <= 20000 <= prerequisites.length <= 5000This is cycle detection in a directed graph — if a cycle exists among the prerequisites, no valid course order can exist.
Kahn's algorithm (BFS): repeatedly remove nodes with zero remaining in-degree; if a cycle exists, some nodes never reach in-degree zero and are never removed.
A DFS-based alternative marks each node's state as unvisited / currently-visiting / fully-visited — revisiting a currently-visiting node mid-DFS is exactly what detecting a 'back edge' (a cycle) looks like.
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] pre : prerequisites) {
adj.get(pre[1]).add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++)
if (inDegree[i] == 0) queue.offer(i);
int processed = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
processed++;
for (int next : adj.get(course)) {
if (--inDegree[next] == 0) queue.offer(next);
}
}
return processed == numCourses;
}Time: O(V+E) · Space: O(V+E)