210. Course Schedule II

Same as Course Schedule (207) but instead of returning a boolean, return the ordering in which courses should be taken. If impossible (cycle), return an empty array.

• 1 ≤ numCourses ≤ 2000
• 0 ≤ prerequisites.length ≤ 5000

Real-world analogy: Project task sequencing

Only change from Course Schedule I

Replace completed += 1 with order.append(cur). The algorithm is identical — you just collect the processing sequence instead of counting it. Return order if len(order) == numCourses, else [].

Visualizer — Kahn's BFS with Order Output

Node label = course · small label = position in order (#N) or remaining in-degree

DFS Approach — Post-order = reverse topological sort

def findOrder(self, numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        adj[b].append(a)
    # 0 = unvisited, 1 = in path, 2 = done
    state = [0] * numCourses
    order = []

    def dfs(node):
        if state[node] == 1: return False  # cycle
        if state[node] == 2: return True
        state[node] = 1
        for nei in adj[node]:
            if not dfs(nei): return False
        state[node] = 2
        order.append(node)   # post-order = reverse topo
        return True

    for i in range(numCourses):
        if not dfs(i): return []
    return order[::-1]      # reverse post-order

Common pitfalls

Multiple valid answers

When two courses both have in-degree 0 at the same time, either can go first. Kahn's BFS produces one valid topological order — any valid order is accepted.

DFS post-order needs reversing

DFS explores deep first, appending a node only after all its dependents are processed. This gives reverse-topological order — you must reverse the list at the end. BFS naturally gives the correct forward order.

What to do next

• 207. Course ScheduleMediumSimpler version — just detect if a cycle exists, no need to track order.›
• 261. Graph Valid TreeMediumAnother cycle-detection problem on undirected graphs.›