Core Insight A visited structure makes each vertex’s work happen at most once.
Common Pitfall Mark a node visited when it is scheduled, not after duplicate work is queued.
Description
Return ordering of courses to finish all courses.
Constraints
- Time Complexity:
O(V+E) - Space Complexity:
O(V+E)
Tags
dfsbfsgraphtopological-sort
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a start node or component.
- Add it to the traversal frontier.
- Visit valid unseen neighbors.
- Repeat for every remaining component if needed.
def findOrder(numCourses, prerequisites):
prereq = {c: [] for c in range(numCourses)}
for crs, pre in prerequisites:
prereq[crs].append(pre)
output = []
visit, cycle = set(), set()
def dfs(crs):
if crs in cycle:
return False
if crs in visit:
return True
cycle.add(crs)
for pre in prereq[crs]:
if dfs(pre) == False: return False
cycle.remove(crs)
visit.add(crs)
output.append(crs)
return True
for c in range(numCourses):
if dfs(c) == False:
return []
return output