Smallest Topological Order

Problem

Return the lexicographically smallest topological order of a directed graph.

Run Kahn's algorithm but keep the ready set in a min-heap so the smallest available node is always emitted next. edges is a list of directed [u, v] pairs. If the graph has a cycle, return an empty list.

Hint

Swapping the queue for a heap turns any Kahn order into the smallest one.

Test cases

case 1

in: [4,[[0,1],[0,2],[1,3],[2,3]]]

expected: [0,1,2,3]

case 2

in: [3,[[2,0],[2,1]]]

expected: [2,0,1]

case 3

in: [3,[[0,1],[1,2],[2,0]]]

expected: []

case 4

in: [1,[]]

expected: [0]

case 5

in: [4,[[3,1],[1,0]]]

expected: [2,3,1,0]

Starter codePython

import heapq

def smallest_topological_order(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor