Topological Sort (Kahn)

Problem

Return the lexicographically smallest topological order of a directed graph with n nodes.

edges is a list of [u, v] pairs meaning u must come before v. Use Kahn's algorithm and always remove the smallest available node with in-degree 0. Return an empty list when the graph has a cycle.

Hint

A min-heap of in-degree zero nodes gives the smallest order.

Test cases

case 1

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

expected: [0,1,2,3]

case 2

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

expected: [0,1,2]

case 3

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

expected: []

case 4

in: [1,[]]

expected: [0]

case 5

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

expected: [0,1,2]

Starter codePython

import heapq
def topological_sort(n, edges):
    # Your code here
    pass

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