AAlgoLab
ALG-H012HardGraphs

Smallest Valid Task Schedule

For tasks numbered 0 through n-1, directed edge [u,v] requires u before v. Return the lexicographically smallest valid full ordering, or [] if dependencies contain a cycle.

Contract

input n: integer
input edges: integer[][]
return integer[]

Constraints

  • • n >= 1
  • • No duplicate edges
  • • 0 <= node id < n

Examples

Example 1
n = 4
edges = [[0, 2], [1, 2], [2, 3]]
→ [0, 1, 2, 3]
Example 2
n = 2
edges = [[0, 1], [1, 0]]
→ []

5 judge tests (2 shown above). Target complexity: O((V+E) log V).