Given a directed acyclic graph (DAG) with V vertices (0 .. V-1) and directed edges edges (each [u, v] means u must come before v), return a topological ordering — a linear order where every edge points forward. If several are valid, return the lexicographically smallest one.
Input: V = 4, edges = [[0,1],[0,2],[1,3],[2,3]] Output: [0, 1, 2, 3] 0 first; then 1 before 2 (smaller); then 3.
Input: V = 3, edges = [[2,0],[2,1]] Output: [2, 0, 1] 2 must precede both 0 and 1; then 0 before 1.
- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - the graph is a DAG (no cycle) - edges are directed u -> v
A topological order lists a DAG's vertices so every edge u → v has u before v — the order you'd complete tasks with dependencies. Kahn's algorithm builds it from in-degrees: a vertex with in-degree 0 has no unmet prerequisite, so it can go next; output it and decrement its successors' in-degrees, exposing new zeros.
When multiple vertices have in-degree 0 at once, any is valid — so to pin down the lexicographically smallest order, always take the smallest-labelled available vertex. A min-heap does this in O((V+E) log V); the brute version rescans all vertices for the smallest zero each step (O(V²)).
“Which order if several are valid?”
The lexicographically smallest.
“Is the graph guaranteed acyclic?”
Yes — it's a DAG, so a full ordering always exists.
I use Kahn's algorithm: repeatedly output an in-degree-0 vertex and decrement its successors.
To get the smallest order I pull the smallest available vertex from a min-heap each step.
Worked example — V = 4, edges [[0,1],[0,2],[1,3],[2,3]]
ready: {0} -> 0
ready: {1,2} -> smallest 1, then 2
ready: {3} -> 3
order = [0, 1, 2, 3]
No unmet prerequisite means the vertex can be output next.
Always emitting the smallest ready vertex is optimal and unique.
Outputting a vertex frees its successors.
| Smallest-zero scan | Kahn's + min-heap | |
|---|---|---|
| Pick next | scan all V for the smallest zero | pop the heap |
| Time | O(V²) | O((V+E) log V) |
| Order | lexicographically smallest | lexicographically smallest |
Both produce the same order; the heap avoids the repeated scan. Full code is in the Approaches selector below.
Key takeaway
Kahn's algorithm: output in-degree-0 vertices, decrementing successors. Use a min-heap to always emit the smallest ready vertex — the lexicographically smallest topological order. O((V+E) log V).
heap = all indeg-0 vertices while heap: u = pop min; output u; for u->w: if --indeg[w]==0 push w