Course Schedule

def canFinish(numCourses, prerequisites):
    taken = [False] * numCourses
    count = 0
    while True:
        # A course is blocked while one of its prerequisites is not taken.
        blocked = [False] * numCourses
        for course, before in prerequisites:
            if not taken[before]:
                blocked[course] = True
        # Take every course that is free this round.
        progress = False
        for c in range(numCourses):
            if not taken[c] and not blocked[c]:
                taken[c] = True
                count += 1
                progress = True
        if not progress:
            break
    return count == numCourses

def canFinish(numCourses, prerequisites):
    unlocks = [[] for _ in range(numCourses)]
    for course, before in prerequisites:
        unlocks[before].append(course)
    # 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
    state = [0] * numCourses
    # next_edge[c] counts the edges out of c the search has already followed.
    next_edge = [0] * numCourses
    for start in range(numCourses):
        if state[start] != 0:
            continue
        # A stack of our own instead of recursion: a chain of 5,000
        # courses would go 5,000 calls deep.
        state[start] = 1
        stack = [start]
        while stack:
            course = stack[-1]
            if next_edge[course] == len(unlocks[course]):
                state[course] = 2
                stack.pop()
                continue
            nxt = unlocks[course][next_edge[course]]
            next_edge[course] += 1
            if state[nxt] == 1:
                return False  # an edge back to the current path closes a cycle
            if state[nxt] == 0:
                state[nxt] = 1
                stack.append(nxt)
    return True

from collections import deque


def canFinish(numCourses, prerequisites):
    # unlocks[b] lists the courses that wait for b.
    # indegree[a] counts the prerequisites of a that are not taken yet.
    unlocks = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for course, before in prerequisites:
        unlocks[before].append(course)
        indegree[course] += 1
    # Every course with no prerequisites can be taken right away.
    queue = deque(c for c in range(numCourses) if indegree[c] == 0)
    taken = 0
    while queue:
        course = queue.popleft()
        taken += 1
        for nxt in unlocks[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    # A course on a cycle never gets down to 0, so it is never taken.
    return taken == numCourses