Pattern: Cycle detection to validate DAG.
function canFinish(numCourses, prerequisites):
adj = build adjacency list from prerequisites
state = array of size numCourses, all UNVISITED
function hasCycle(u):
if state[u] == VISITING:
return true
if state[u] == VISITED:
return false
state[u] = VISITING
for v in adj[u]:
if hasCycle(v):
return true
state[u] = VISITED
return false
for i from 0 to numCourses - 1:
if hasCycle(i):
return false
return true
Alternatively, use Kahn's algorithm. If topo sort produces nodes, no cycle exists.
Time: . Space: .