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.