Course Schedule - Implementation

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 $N$ nodes, no cycle exists.

Time: $O(N + E)$. Space: $O(N)$.