Topological Order (lexicographically smallest)

Difficulty: Hard · Topic: Graphs

Given a DAG with n nodes 0…n-1 and directed edges ([a, b] means a comes before b), return the lexicographically smallest topological ordering. If the graph has a cycle (no valid ordering), return []. Use Kahn's algorithm with a min-heap of zero-in-degree nodes.

Examples

topo_order(4, [[0,1],[0,2],[1,3],[2,3]])
→ [0,1,2,3]

topo_order(2, [[0,1]])
→ [0,1]

Target complexity: time O((V + E) log V), space O(V + E)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.