Lexicographically Smallest Topological Order
MediumGraphTopological SortHeapSortingLinked List
Description
Given n nodes labeled 0..n-1 and a list of directed edges, return the lexicographically smallest topological ordering. If the graph has a cycle, return an empty list.
Examples
Input:
n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]Output:
[0,1,2,3]Explanation:
Diamond DAG; choosing the smallest available label at each step yields [0,1,2,3].
Input:
n = 3, edges = [[0,1],[1,2],[2,0]]Output:
[]Explanation:
The graph 0->1->2->0 contains a cycle, so no topological order exists and the answer is [].
Input:
n = 1, edges = []Output:
[0]Explanation:
A single node with no edges has the trivial topological order [0].
Constraints
- •
1 ≤ n ≤ 1000 - •
0 ≤ edges.length ≤ 5000