Topological Sort

Problem

Given n nodes labelled 0 to n-1 and directed edges as [u, v] pairs forming a DAG, return a topological ordering of all nodes.

Use Kahn's algorithm with a min-heap of zero-indegree nodes so the result is the lexicographically smallest valid order. If a cycle prevents every node from being ordered, return an empty list.

Hint

Repeatedly take the smallest node with indegree zero and relax its outgoing edges.

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: [1,[]]

expected: [0]

case 4

in: [0,[]]

expected: []

case 5

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

expected: [0,1,2,3]

Starter codePython

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

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