Order Classes by Prerequisites with Recursive DFS

Implement class_order(classes, prerequisites) using recursive depth-first search.

classes contains distinct class names. Each item [course, prerequisite] in prerequisites means prerequisite must be completed before course. Return an ordering containing every class exactly once and satisfying every prerequisite.

The result must be deterministic: start DFS roots in the order given by classes, visit each course's prerequisites in the order their pairs appear in prerequisites, and append a course after all of its prerequisites. If the dependency graph contains a cycle, return [].

Function Contract

def class_order(classes: list[str], prerequisites: list[list[str]]) -> list[str]:
    ...

Examples

classes = ["Compilers", "Algorithms", "AI", "Databases"]
prerequisites = [
  ["Compilers", "Algorithms"],
  ["AI", "Algorithms"],
]

result = ["Algorithms", "Compilers", "AI", "Databases"]

classes = ["A", "B", "C"]
prerequisites = [["A", "B"], ["B", "C"], ["C", "A"]]

result = []

Constraints

• 0 <= len(classes) <= 1_000
• 0 <= len(prerequisites) <= 20_000
• Every prerequisite pair contains two names from classes.
• There are no duplicate prerequisite pairs.
• The implementation must use recursive DFS, with enough states to distinguish an active recursion path from a completed node.

Order Classes by Prerequisites with Recursive DFS

Hints

1. Build each course's prerequisite list without reordering the pairs.
2. Three states—unvisited, active, and completed—distinguish a back edge from shared work.
3. Append a course only after every prerequisite DFS returns successfully.

Approach

Store prerequisite adjacency in input order. Recursive DFS marks a class active before descending. Encountering an active class proves a directed cycle; encountering a completed class reuses its already-valid placement. Postorder appending places every prerequisite before its dependent, while the prescribed root and adjacency iteration orders make the result deterministic.

• Time complexity: O(c + p), where c is the number of classes and p is the number of prerequisite pairs.
• Space complexity: O(c + p) for adjacency, state, output, and the recursion stack.