192. Course Schedule Feasibility

Why this mechanism works

Turn each requirement into prerequisite->course. A course becomes available when all its incoming requirements have been removed. Repeatedly process zero-indegree courses and release their dependents. If a cycle remains, its members retain at least one unmet requirement and cannot enter the queue.

State and boundaries

indegree[v] counts prerequisite-edge occurrences from unprocessed courses. The queue contains currently available courses.

Protocol

1. Build outgoing lists and indegrees.
2. Enqueue every zero-indegree course.
3. Process one course and decrement each dependent's indegree.
4. Enqueue a dependent exactly when its count reaches zero.
5. Compare processed count with n.

Visualization

requirements (1,0),(2,1) -> 0 -> 1 -> 2
indegrees [0,1,1]
release 0, then 1, then 2 -> all complete

Python implementation

from collections import deque

def can_finish(n, prerequisites):
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for course, prerequisite in prerequisites:
        adj[prerequisite].append(course)
        indegree[course] += 1
    queue = deque(u for u in range(n) if indegree[u] == 0)
    processed = 0
    while queue:
        u = queue.popleft()
        processed += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return processed == n

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 can_finish: adj = [[] for _ in range(n)]
n=3; prerequisites=[(1, 0), (2, 1)]; _=0

L4 can_finish: adj = [[] for _ in range(n)]
n=3; prerequisites=[(1, 0), (2, 1)]; _=1

L4 can_finish: adj = [[] for _ in range(n)]
n=3; prerequisites=[(1, 0), (2, 1)]; _=2

L4 can_finish: adj = [[] for _ in range(n)]
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[], [], []]

L5 can_finish: indegree = [0] * n
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[], [], []]; indegree=[0, 0, 0]

L6 can_finish: for course, prerequisite in prerequisites:
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[], [], []]; indegree=[0, 0, 0]; course=1; prerequisite=0

L7 can_finish: adj[prerequisite].append(course)
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[1], [], []]; indegree=[0, 0, 0]; course=1; prerequisite=0

L8 can_finish: indegree[course] += 1
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[1], [], []]; indegree=[0, 1, 0]; course=1; prerequisite=0

... 16 intermediate state changes omitted ...

L15 can_finish: indegree[v] -= 1
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[1], [2], []]; indegree=[0, 0, 0]; course=2; prerequisite=1; queue=deque([]); processed=2; u=1; v=2

L17 can_finish: queue.append(v)
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[1], [2], []]; indegree=[0, 0, 0]; course=2; prerequisite=1; queue=deque([2]); processed=2; u=1; v=2

L12 can_finish: u = queue.popleft()
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[1], [2], []]; indegree=[0, 0, 0]; course=2; prerequisite=1; queue=deque([]); processed=2; u=2; v=2

L13 can_finish: processed += 1
n=3; prerequisites=[(1, 0), (2, 1)]; adj=[[1], [2], []]; indegree=[0, 0, 0]; course=2; prerequisite=1; queue=deque([]); processed=3; u=2; v=2

L4 can_finish: adj = [[] for _ in range(n)]
n=2; prerequisites=[(1, 0), (0, 1)]; _=0

L4 can_finish: adj = [[] for _ in range(n)]
n=2; prerequisites=[(1, 0), (0, 1)]; _=1

L4 can_finish: adj = [[] for _ in range(n)]
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[], []]

L5 can_finish: indegree = [0] * n
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[], []]; indegree=[0, 0]

L6 can_finish: for course, prerequisite in prerequisites:
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[], []]; indegree=[0, 0]; course=1; prerequisite=0

L7 can_finish: adj[prerequisite].append(course)
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], []]; indegree=[0, 0]; course=1; prerequisite=0

L8 can_finish: indegree[course] += 1
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], []]; indegree=[0, 1]; course=1; prerequisite=0

L6 can_finish: for course, prerequisite in prerequisites:
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], []]; indegree=[0, 1]; course=0; prerequisite=1

... 2 intermediate state changes omitted ...

L9 <genexpr>: queue = deque(u for u in range(n) if indegree[u] == 0)
.0=range_iterator; u=0; indegree=[1, 1]

L9 <genexpr>: queue = deque(u for u in range(n) if indegree[u] == 0)
.0=range_iterator; u=1; indegree=[1, 1]

L9 can_finish: queue = deque(u for u in range(n) if indegree[u] == 0)
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], [0]]; indegree=[1, 1]; course=0; prerequisite=1; queue=deque([])

L10 can_finish: processed = 0
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], [0]]; indegree=[1, 1]; course=0; prerequisite=1; queue=deque([]); processed=0

Why the solution is correct

Each processed course has no remaining prerequisite, so the produced prefix is feasible. If processing stops early, every remaining vertex has an incoming edge from the remaining graph; following predecessors in a finite set yields a cycle. Conversely, a cycle can never release its own first member.

Time and space

O(n+m) time and space for m prerequisite pairs.

Common mistakes

Reversing pair meaning changes the intended order even though cycle existence may remain the same. Deduplicating adjacency without also deduplicating indegrees can leave counts permanently positive.

Reasoning card

Transfer exercise

Return the unprocessed courses after failure. Explain why they can include descendants of cycles as well as cycle members.