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
Determine if you can finish all courses (cycle detection).
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 canFinish(numCourses, prerequisites):
preMap = {i: [] for i in range(numCourses)}
for crs, pre in prerequisites:
preMap[crs].append(pre)
visitSet = set()
def dfs(crs):
if crs in visitSet:
return False
if preMap[crs] == []:
return True
visitSet.add(crs)
for pre in preMap[crs]:
if not dfs(pre): return False
visitSet.remove(crs)
preMap[crs] = []
return True
for crs in range(numCourses):
if not dfs(crs): return False
return True