Topological Sort

Problem Given a directed acyclic graph, produce a valid topological ordering of its nodes — a linear order in which, for every edge u → v, u appears before v.

Input / Output

• Input: n nodes labelled 0..n-1 and a list of directed edges, typically supplied as an adjacency list.
• Output: an array containing all n nodes in a valid topological order; if the graph contains a cycle, report that no ordering exists.

Constraints

• 1 <= n <= 10^5 with edges up to ~2·10^5, so the algorithm must be linear in V+E.
• The ordering is not unique — any valid one is accepted unless a tie-break rule is specified.
• The graph may be disconnected, so every component must be seeded, not just one start node.

Example

• Edges 5→0, 5→2, 4→0, 4→1, 2→3, 3→1 → one valid order is [4,5,2,3,1,0]; [5,4,2,3,1,0] is equally valid.
• Adding the edge 1→5 closes a cycle 5→2→3→1→5, so no ordering exists.