Course Schedule (Detect Cycle)
There are numCourses labeled 0..n-1 and prerequisites [a,b] meaning b before a. Return true if you can finish all courses (i.e., the graph is a DAG).
Answers use simple, clear English.
Quick interview answer
Build adjacency list and indegrees; Kahn's BFS topological sort. If you process fewer than n nodes, a cycle exists. DFS coloring (white/gray/black) also detects back edges.
Detailed answer
Build adjacency list and indegrees; Kahn's BFS topological sort. If you process fewer than n nodes, a cycle exists. DFS coloring (white/gray/black) also detects back edges. Interviewers often ask both cycle detection and the actual order.
Full explanation
Interviewers often ask both cycle detection and the actual order.
Real example & use case
Learning-path builder blocking enrollment when required courses form a cycle.
Pros & cons
Pros: Kahn gives order + cycle check. Cons: adjacency build is O(V+E).
Code example
from collections import deque, defaultdict
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
graph = defaultdict(list)
indeg = [0] * num_courses
for a, b in prerequisites:
graph[b].append(a)
indeg[a] += 1
q = deque([i for i, d in enumerate(indeg) if d == 0])
seen = 0
while q:
u = q.popleft()
seen += 1
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return seen == num_coursesPractice code · python (view only · no execution)
from collections import deque, defaultdict
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
graph = defaultdict(list)
indeg = [0] * num_courses
for a, b in prerequisites:
graph[b].append(a)
indeg[a] += 1
q = deque([i for i, d in enumerate(indeg) if d == 0])
seen = 0
while q:
u = q.popleft()
seen += 1
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return seen == num_courses