2. Course Schedule (Topological Sort + Cycle Detection)

Problem

A training/eval pipeline is made of stages with hard sequential dependencies — e.g. "tokenize" must run before "train," and "train" must run before "eval." Before submitting a pipeline to the scheduler, validate that its dependency graph is actually runnable: given the number of stages and a list of prerequisite pairs, determine whether all stages can be completed, i.e. whether the dependency graph is a DAG (no cycle).

Stages are numbered 0..num_stages-1. Each prerequisite entry is (stage, prereq), meaning stage depends on prereq completing first.

Source: src/2_course_schedule_cycle_detection.py

def can_complete_all_stages(num_stages: int, prerequisites: list[tuple[int, int]]) -> bool: ...

>>> can_complete_all_stages(4, [(1, 0), (2, 1), (3, 2)])
True

>>> can_complete_all_stages(2, [(0, 1), (1, 0)])
False

Step-by-Step Approach

1. Build an adjacency list from the prerequisite pairs: for each (stage, prereq), add an edge prereq -> stage (prereq unlocks stage).
2. Compute each stage's indegree — the number of unfinished prerequisites still blocking it. Stages that start with indegree 0 have no prerequisites and can run immediately.
3. Seed a queue with every indegree-0 stage. This is Kahn's algorithm: repeatedly "complete" a stage from the queue, then decrement the indegree of every stage it unlocks.
4. Whenever decrementing a downstream stage's indegree brings it to 0, all of its prerequisites are now satisfied — push it onto the queue too.
5. Count how many stages get processed this way in total.
6. If every stage was eventually processed, the graph is a DAG (no cycle) and can_complete_all_stages returns True. If some stages never reach indegree 0 — because they're stuck in a cycle where each is waiting on another that's waiting on it — they're left unprocessed, and the count comes up short, so the function returns False.

The key insight is that a cycle is exactly the set of nodes that Kahn's algorithm can never "unlock," because every node in a cycle depends on another node in the same cycle, so none of them can ever reach indegree zero on their own — comparing the processed count to the total node count is a cheap, direct way to detect that without any separate DFS-based cycle check.

Reference solution

from collections import deque


def can_complete_all_stages(num_stages: int, prerequisites: list[tuple[int, int]]) -> bool:
    # Kahn's algorithm: repeatedly peel off indegree-0 nodes; if every node
    # eventually gets peeled, the graph is acyclic. O(V + E) time/space.
    graph: dict[int, list[int]] = {stage: [] for stage in range(num_stages)}
    indegree = [0] * num_stages
    for stage, prereq in prerequisites:
        graph[prereq].append(stage)
        indegree[stage] += 1

    queue = deque(stage for stage in range(num_stages) if indegree[stage] == 0)
    processed = 0
    while queue:
        node = queue.popleft()
        processed += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    return processed == num_stages  # leftover nodes mean a cycle held them back

Key Functions & Tricks

• collections.deque — O(1) pops from the front, unlike a plain list.
• Indegree array — tracks how many unmet prerequisites remain per stage, updated incrementally rather than recomputed.
• Kahn's algorithm (BFS-based topological sort) — repeatedly consumes indegree-0 nodes; naturally produces a valid run order as a side effect (not used here, but processed == num_stages is the acyclicity check derived from it).
• processed == num_stages — the whole cycle-detection logic reduces to this one comparison; no separate visited/recursion-stack DFS is needed.
• Dict comprehension for the adjacency list — initializes every stage's edge list up front, even ones with no outgoing edges.

How to Recognize This Pattern