Unique Topological Order Check

Problem

Decide whether a directed graph has exactly one topological order.

Run Kahn's algorithm and check that at every step there is exactly one node with in-degree 0. Return False when the graph has a cycle, since it then has no topological order at all. edges is a list of [u, v] pairs.

Hint

A unique topological order is equivalent to the DAG having a Hamiltonian path.

Test cases

case 1

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

expected: true

case 2

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

expected: false

case 3

in: [1,[]]

expected: true

case 4

in: [2,[]]

expected: false

case 5

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

expected: true

Starter codePython

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

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