MediumGraphTopological SortBFS·AmazonGoogle⚡ Very Frequent
You are given numCourses courses (0 to n-1) and an array prerequisites where [a, b] means you must take course b before a. Return true if all courses can be finished, false if there is a cycle.
1 ≤ numCourses ≤ 2000
0 ≤ prerequisites.length ≤ 5000
Example 1
numCourses2
prerequisites[[1,0]]
Outputtrue
Example 2 (cycle)
prerequisites[[0,1],[1,0]]
Outputfalse
Real-world analogy: University course planner
🎓 Prerequisite chain: You're planning your college schedule. Some courses require others first (e.g., "Calculus 2 requires Calculus 1"). Can you take every course without being stuck in an impossible loop?
A cycle means two courses require each other — deadlock. You can never start either. Kahn's algorithm (BFS topological sort) simulates a real student: take courses with zero remaining prerequisites, complete them, which may unlock new courses. If you complete all n courses — no cycle. If you get stuck — cycle exists.
The in-degree of a course = number of prerequisites not yet taken. When in-degree reaches 0, that course is ready to take.
Algorithm — Kahn's BFS (Topological Sort)
1. Build adjacency list + compute in-degrees. 2. Enqueue all courses with in-degree 0. 3. While queue not empty: Dequeue course, completed++ For each neighbor: indegree[nei]-- If indegree[nei] == 0 → enqueue nei 4. Return completed == numCourses
Approach
Time
Space
Notes
DFS (cycle detection)
O(V+E)
O(V+E)
3-color DFS: white/gray/black
Kahn's BFS ✓
O(V+E)
O(V+E)
Iterative, easy to extend to return order
Visualizer — Kahn's BFS Topological Sort
Node label = course · in:N = remaining prerequisites ● Amber = queued · ● Orange = processing · ● Green = completed · ● Red = in cycle
COMPLETED
0/?
BFS QUEUE
(empty)
KAHN'S BFS—
Press ▶ or step forward to begin.
✓
—
SpacePlay/Pause ←→Step R Reset F Fullscreen
Executing Code
defcanFinish(self, numCourses, prerequisites):
adj = [[] for _ inrange(numCourses)]
indegree = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a); indegree[a] += 1
q = deque(i for i inrange(numCourses) if indegree[i]==0)
completed = 0
while q:
cur = q.popleft(); completed += 1
for nei in adj[cur]:
indegree[nei] -= 1
if indegree[nei] == 0:
q.append(nei)
return completed == numCourses
DFS Approach — Cycle detection
Use 3 states: unvisited (0), in current path (1), done (2). A back-edge to state 1 = cycle.
dfs.py
def canFinish(self, numCourses, prerequisites):
adj = [[] for _ in range(numCourses)]
for a, b in prerequisites:
adj[b].append(a)
# 0 = unvisited, 1 = in current path, 2 = done
state = [0] * numCourses
def dfs(node):
if state[node] == 1: return False # cycle!
if state[node] == 2: return True # already checked
state[node] = 1
for nei in adj[node]:
if not dfs(nei): return False
state[node] = 2
return True
return all(dfs(i) for i in range(numCourses))
Common pitfalls
Building the graph backwards
[a, b] means b → a (b must come before a). The edge goes from prerequisite b to dependent course a. Getting this backwards means your in-degrees are wrong and cycles go undetected.
Checking queue empty vs. completed count
Don't return true just because the queue is empty — the queue empties when nodes get stuck in a cycle too. Always check completed == numCourses.
Pattern: Kahn's BFS Topological Sort
In-degree 0 = no remaining dependencies → process first.
Each processed node reduces its neighbors' in-degrees.
If all nodes processed → DAG (no cycle). Else → cycle.
Discussion
…