Course schedule

This is a directed graph. Repeatedly take any course with no remaining prerequisites. If you get stuck before taking everything, there must be a cycle.

from collections import deque

def can_finish(n, prereqs):
    needs = [0] * n
    unlocks = [[] for _ in range(n)]
    for course, before in prereqs:
        needs[course] += 1
        unlocks[before].append(course)
    ready = deque(c for c in range(n) if needs[c] == 0)
    done = 0
    while ready:
        c = ready.popleft()
        done += 1
        for nxt in unlocks[c]:
            needs[nxt] -= 1
            if needs[nxt] == 0:
                ready.append(nxt)
    return done == n

This is Kahn's algorithm for topological sorting. needs counts unmet prerequisites; finishing a course unlocks the ones that depended on it. Courses in a cycle never reach zero, so done falls short. O(n + number of prerequisites). Build tools and package managers solve the same problem to order their steps.