the trick
Prerequisites form a directed graph; you can finish all courses if and only if that graph has no cycle. Color each node white/gray/black and a cycle is exactly an edge back to a gray node.
The question behind the question
You get numCourses and pairs [a, b] meaning "to take a you must first take
b". The question is whether some order lets you finish everything.
Model each course as a node and each prerequisite as a directed edge b -> a.
You can finish all courses exactly when this graph has no cycle: a cycle is a set
of courses that all wait on each other, so none can start.
Three-color DFS
The real work is just cycle detection. I run DFS and color each node white
(unvisited), gray (on the current recursion stack), or black (fully explored and
safe). If DFS reaches a gray node, that node is an ancestor of itself (a cycle),
so the answer is False. Once a node finishes I paint it black so later calls
skip it. Each node is colored once and each edge walked once.
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
graph: dict[int, list[int]] = {c: [] for c in range(num_courses)}
for course, prereq in prerequisites:
graph[prereq].append(course)
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * num_courses
def has_cycle(node: int) -> bool:
color[node] = GRAY
for nxt in graph[node]:
if color[nxt] == GRAY:
return True
if color[nxt] == WHITE and has_cycle(nxt):
return True
color[node] = BLACK
return False
return not any(has_cycle(c) for c in range(num_courses) if color[c] == WHITE)Why the colors are enough
Gray is the key. A back edge to a black node is fine. That subtree was already cleared. A back edge to a gray node means you looped onto the current path, which is exactly a cycle. Starting DFS from every white node covers disconnected components, and the black marking stops re-exploration.
O(V + E) time and space for the adjacency list and recursion.