Course Schedule

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

Course Schedule. You have courses numbered from zero, and a list of prerequisite pairs: take this one before that one. Can you finish every course?

Picture six levels on a map. Zero leads to one and four. Three also leads to one. One and four lead to two, and two leads to five. Each lock counts the prerequisites a level still needs.

Trying every order is hopeless: six courses already have seven hundred twenty. And the real trap is a loop. If courses wait on each other in a circle, none can ever go first.

So keep counts instead. A level with zero locks is ready, so it waits in a queue. Take one, clear it, and each level it leads to loses a lock. When a count hits zero, that level joins the queue.

In code, list what each course unlocks and count its prerequisites. Queue every zero. Pop a course, count it as taken, and remove one lock from each next course, queueing new zeros. You finish only if taken equals the number of courses.

Let's play it. Zero and three start ready. Take zero: one drops to one, four drops to zero. Take three: one opens. Take four: two drops to one. Take one: two opens. Then two, then five. Six of six, so yes.

Now the loop. Zero needs one, one needs two, two needs zero. Every lock starts at one, the queue starts empty, and nothing is ever taken. Zero of three, so no.

Each course is queued once and each prerequisite crossed once, so time and space are both O of V plus E.

Clear what's ready, unlock what's next. That's Course Schedule.