193. Return One Course Order

Why this mechanism works

Keep the actual sequence from the feasibility algorithm. Every popped vertex can safely follow the existing prefix because all of its prerequisites already appear there. A reusable adjacency-list topological_order helper makes that guarantee available to the following DAG problems.

State and boundaries

order is a valid topological prefix. indegree counts incoming edges whose sources are outside that prefix.

Protocol

1. Build prerequisite-to-course edges.
2. Initialize all indegrees and zero-indegree queue.
3. Append each popped vertex to order.
4. Release outgoing neighbors.
5. Return order only if its length equals n.

Visualization

ready [0,1]; order []
pop 0, release 2 -> ready [1,2]
pop 1, then 2 -> valid prefix grows monotonically

Python implementation

from collections import deque

def topological_order(adj):
    indegree = [0] * len(adj)
    for neighbors in adj:
        for v in neighbors:
            indegree[v] += 1
    queue = deque(u for u, degree in enumerate(indegree) if degree == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == len(adj) else []

def course_order(n, prerequisites):
    adj = [[] for _ in range(n)]
    for course, prerequisite in prerequisites:
        adj[prerequisite].append(course)
    return topological_order(adj)

Worked execution

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

L20 course_order: adj = [[] for _ in range(n)]
n=4; prerequisites=[(1, 0), (2, 0), (3, 1), (3, 2)]; _=0

L20 course_order: adj = [[] for _ in range(n)]
n=4; prerequisites=[(1, 0), (2, 0), (3, 1), (3, 2)]; _=1

L20 course_order: adj = [[] for _ in range(n)]
n=4; prerequisites=[(1, 0), (2, 0), (3, 1), (3, 2)]; _=2

L20 course_order: adj = [[] for _ in range(n)]
n=4; prerequisites=[(1, 0), (2, 0), (3, 1), (3, 2)]; _=3

L20 course_order: adj = [[] for _ in range(n)]
n=4; prerequisites=[(1, 0), (2, 0), (3, 1), (3, 2)]; adj=[[], [], [], []]

L21 course_order: for course, prerequisite in prerequisites:
n=4; prerequisites=[(1, 0), (2, 0), (3, 1), (3, 2)]; adj=[[], [], [], []]; course=1; prerequisite=0

L22 course_order: adj[prerequisite].append(course)
n=4; prerequisites=[(1, 0), (2, 0), (3, 1), (3, 2)]; adj=[[1], [], [], []]; course=1; prerequisite=0

L21 course_order: for course, prerequisite in prerequisites:
n=4; prerequisites=[(1, 0), (2, 0), (3, 1), (3, 2)]; adj=[[1], [], [], []]; course=2; prerequisite=0

... 36 intermediate state changes omitted ...

L14 topological_order: indegree[v] -= 1
adj=[[1, 2], [3], [3], []]; indegree=[0, 0, 0, 0]; neighbors=[]; v=3; queue=deque([]); order=[0, 1, 2]; u=2

L16 topological_order: queue.append(v)
adj=[[1, 2], [3], [3], []]; indegree=[0, 0, 0, 0]; neighbors=[]; v=3; queue=deque([3]); order=[0, 1, 2]; u=2

L11 topological_order: u = queue.popleft()
adj=[[1, 2], [3], [3], []]; indegree=[0, 0, 0, 0]; neighbors=[]; v=3; queue=deque([]); order=[0, 1, 2]; u=3

L12 topological_order: order.append(u)
adj=[[1, 2], [3], [3], []]; indegree=[0, 0, 0, 0]; neighbors=[]; v=3; queue=deque([]); order=[0, 1, 2, 3]; u=3

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

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

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

L21 course_order: for course, prerequisite in prerequisites:
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[], []]; course=1; prerequisite=0

L22 course_order: adj[prerequisite].append(course)
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], []]; course=1; prerequisite=0

L21 course_order: for course, prerequisite in prerequisites:
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], []]; course=0; prerequisite=1

L22 course_order: adj[prerequisite].append(course)
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], [0]]; course=0; prerequisite=1

L4 topological_order: indegree = [0] * len(adj)
adj=[[1], [0]]; indegree=[0, 0]

... 6 intermediate state changes omitted ...

L8 <genexpr>: queue = deque(u for u, degree in enumerate(indegree) if degree == 0)
.0=enumerate; u=0; degree=1

L8 <genexpr>: queue = deque(u for u, degree in enumerate(indegree) if degree == 0)
.0=enumerate; u=1; degree=1

L8 topological_order: queue = deque(u for u, degree in enumerate(indegree) if degree == 0)
adj=[[1], [0]]; indegree=[1, 1]; neighbors=[0]; v=0; queue=deque([])

L9 topological_order: order = []
adj=[[1], [0]]; indegree=[1, 1]; neighbors=[0]; v=0; queue=deque([]); order=[]

Why the solution is correct

Every appended vertex has zero remaining indegree, so all of its predecessors precede it. Hence a full result respects every edge. If fewer than n vertices are processed, the remaining directed cycle prevents any full ordering, justifying the empty failure result.

Time and space

O(V+E) time and space for the generic helper; O(n+m) for courses.

Common mistakes

Returning a partial order on failure violates the all-courses contract. A FIFO queue does not maintain smallest available vertex after later releases.

Reasoning card

Transfer exercise

Replace the FIFO queue with a min-heap to obtain the lexicographically smallest valid order.