Topological sort of a directed graph

Problem Given a directed acyclic graph (DAG) with V vertices and E edges, return a valid topological ordering of its vertices — an ordering in which, for every directed edge u -> v, u appears before v. If the graph contains a cycle, report that no valid ordering exists.

Input / Output

• Input: number of vertices and a list of directed edges (adjacency list).
• Output: a list of vertices in a valid topological order (any valid order is accepted), or an indication that none exists.

Constraints

• 1 <= V <= 10^5, 0 <= E <= 2*10^5. Multiple valid orderings may exist.

Example

• Edges 5->2, 5->0, 4->0, 4->1, 2->3, 3->1 -> a valid order is [4, 5, 2, 3, 1, 0].

Expected approach

• Kahn's algorithm (BFS on in-degrees): repeatedly emit a zero-in-degree vertex and decrement its neighbours; if fewer than V vertices are emitted, a cycle exists. Alternatively, DFS with a finish-time stack. Both run in O(V + E) time and O(V) space.