There are numCourses courses numbered 0 .. numCourses-1. Each prerequisite
a,b means you must take course b before course a. Return true if it's
possible to finish all the courses — i.e. the prerequisite graph has no cycle.
prereqsPossible(numCourses, prereqs)
Input format: n | edges, where edges are a,b pairs of course numbers.
3 courses, prereqs (0,1)(1,2) // → true
3 courses, prereqs (0,1)(1,2)(2,0) // → false (cyclic)
2 courses, no prereqs // → true
The first move on a word problem like this is finding the graph hiding inside it. Courses are nodes; each prerequisite pair means "take b before a," a directed edge from a to b. Once you've made that translation, "can I finish all courses" stops being about scheduling and becomes a pure graph question.
If course x needs y, y needs z, and z needs x again, then taking x needs y, which needs z, which needs x — an infinite regress with no valid starting point. That's exactly what a cycle represents.
Conversely, an acyclic graph always has a valid order: find a course with no unfinished prerequisites, take it, remove it, repeat. A cycle is the only thing that could prevent such a course from ever existing. So the whole question reduces to: is this directed graph acyclic?
This is the has-cycle problem in a course-scheduling costume. Build the directed graph from the prerequisite pairs, then run the same three-colour DFS. If it ever reaches a grey node, you've found a circular dependency — finishing all courses is impossible.
Any "is this ordering achievable" problem — build systems, spreadsheet formulas, task schedulers — reduces to the same question: model dependencies as directed edges, check whether the graph is acyclic. Spotting that pattern is usually the whole difficulty; the cycle-detection mechanics are always the same three-colour DFS.
def prereqs_possible(num_courses, prereqs):
graph = {i: [] for i in range(num_courses)}
for a, b in prereqs:
graph[a].append(b)
WHITE, GREY, BLACK = 0, 1, 2
state = {}
def dfs(node):
state[node] = GREY
for nxt in graph.get(node, []):
if state.get(nxt, WHITE) == GREY:
return True
if state.get(nxt, WHITE) == WHITE and dfs(nxt):
return True
state[node] = BLACK
return False
for i in range(num_courses):
if state.get(i, WHITE) == WHITE and dfs(i):
return False
return True
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.