Approach Summary
Detect cycle in directed graph using DFS (3-color states) or Kahn's BFS topological sort. If cycle exists, impossible.
Full Solution & Approach
This is cycle detection on a directed graph, solved with Kahn's algorithm — topological sort via indegrees. Each course is a node; each prerequisite pair (a, b) is an edge b → a. Compute the indegree of every node. Any course with indegree 0 can be taken immediately — put it in a queue. Repeatedly take a course off the queue, "remove" it by decrementing the indegree of every course that depends on it, and whenever a dependent's indegree hits 0, add it to the queue. Count how many courses you processed. If the count equals numCourses, every course is reachable and the dependency graph is acyclic — return true. If you processed fewer, a cycle remains (all leftover courses depend on each other), so completion is impossible. BFS order does not matter here — only the count.
Each edge is relaxed once when its source is processed — O(V + E) time. The adjacency lists, indegree array, and queue use O(V + E) space.
Solution Code
Solution
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
queue = [c for c in range(num_courses) if indegree[c] == 0]
processed = 0
for c in queue:
processed += 1
for nxt in graph[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return processed == num_coursesfunction canFinish(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
indegree[course]++;
}
const queue = [];
for (let c = 0; c < numCourses; c++) {
if (indegree[c] === 0) queue.push(c);
}
let processed = 0;
for (let i = 0; i < queue.length; i++) {
processed++;
for (const nxt of graph[queue[i]]) {
if (--indegree[nxt] === 0) queue.push(nxt);
}
}
return processed === numCourses;
}public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]);
indegree[p[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int c = 0; c < numCourses; c++) if (indegree[c] == 0) queue.offer(c);
int processed = 0;
while (!queue.isEmpty()) {
int c = queue.poll();
processed++;
for (int next : graph.get(c)) {
if (--indegree[next] == 0) queue.offer(next);
}
}
return processed == numCourses;
}bool canFinish(int numCourses, const vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (auto& p : prerequisites) {
graph[p[1]].push_back(p[0]);
indegree[p[0]]++;
}
queue<int> q;
for (int c = 0; c < numCourses; c++) if (indegree[c] == 0) q.push(c);
int processed = 0;
while (!q.empty()) {
int c = q.front(); q.pop();
processed++;
for (int next : graph[c]) {
if (--indegree[next] == 0) q.push(next);
}
}
return processed == numCourses;
}Edge Cases to Watch
- No prerequisites — every course has indegree 0, returns true
- A direct cycle like a depends on b and b depends on a
- numCourses larger than the courses referenced in prerequisites — isolated courses are trivially completable
- Multiple connected components — handled naturally
How to Recognize This Pattern
- Prerequisite ordering
- Can all courses be taken?
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V + E)