Course Schedule II

Run the same cycle-detecting DFS as Course Schedule, but this time append each course to an order list right after all of its dependencies have finished processing. Because a course is only appended once every course it depends on is already in order, the list comes out in a valid dependency order directly (no reversal needed).

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[a].append(b)

        UNVISITED, VISITING, DONE = 0, 1, 2
        state = [UNVISITED] * numCourses
        order = []

        def dfs(u):
            if state[u] == VISITING:
                return False
            if state[u] == DONE:
                return True

            state[u] = VISITING
            for v in graph[u]:
                if not dfs(v):
                    return False
            state[u] = DONE
            order.append(u)
            return True

        for u in range(numCourses):
            if not dfs(u):
                return []
        return order

Tracing on the example, looping dfs(0) through dfs(3):

1. dfs(0): no dependencies. Append 0. order = [0].
2. dfs(1): depends on 0, already DONE. Append 1. order = [0, 1].
3. dfs(2): depends on 0, already DONE. Append 2. order = [0, 1, 2].
4. dfs(3): depends on 1 and 2, both already DONE. Append 3. order = [0, 1, 2, 3].

Why it’s correct: a node is appended to order only after every node it depends on is already in order (either appended earlier or confirmed DONE in this call), so by induction every dependency precedes its dependent in the final list. Complexity: each node is visited once and each edge is followed once → O(V + E) time, O(V + E) space for the graph, color array, and recursion stack.

Build the graph pointing prerequisite → dependent, track in-degrees (number of unmet prerequisites), and repeatedly dequeue courses with in-degree 0 — courses that are ready to take right now — appending each to the result as it’s dequeued.

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indegree[a] += 1

        queue = deque(u for u in range(numCourses) if indegree[u] == 0)
        order = []

        while queue:
            u = queue.popleft()
            order.append(u)
            for v in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)

        return order if len(order) == numCourses else []

Play through the same example — n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Watch the in-degree badges feed the ready queue, and the queue feed the order below — every pop is one course locked into the answer:

A cycle flips the answer to [] — a queue that runs dry without finishing every course is a queue that got stuck. On n = 3, prerequisites = [[1,0],[2,1],[1,2]], courses 1 and 2 wait on each other. Watch the queue seed, pop course 0, and then die:

Why it’s correct: a course reaches in-degree 0 exactly when every course it depends on has already been dequeued (placed earlier in order), so appending it at that moment preserves every dependency constraint. If a cycle exists, every course in it keeps at least one un-decremented in-degree forever, so order never reaches length numCourses, correctly signaling impossibility. Complexity: each node is enqueued once and each edge decrements one counter → O(V + E) time, O(V + E) space. Same complexity as the DFS version, but iterative — no recursion depth to worry about on graphs with long chains, and the ready-to-take intuition maps directly onto how you’d actually plan the courses.