Topological sort
Filed under Flipkart · Also reported at ClearTrip, Happiest Mind, Innovaccer, Magnitude Software, Moonfrog Labs, Nielsen, OYO, Paytm and 1 more
Free read 2 of 3Confirm graph representation and check if the graph is guaranteed to be a DAG.
The question
Given a directed acyclic graph (DAG), return a linear ordering of its vertices such that for every directed edge u -> v from vertex u to vertex v, u comes before v in the ordering.
Constraints
- The graph is represented as an adjacency list.
- The graph is guaranteed to be a Directed Acyclic Graph (DAG).
- Number of vertices V <= 10^5, Edges E <= 2 * 10^5.
Examples
- Input
- n = 6, edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]
- Output
- [4, 5, 2, 3, 1, 0]
- Why
- Vertex 4 and 5 have in-degree 0. Processing them leads to a valid topological order.
Approach
Confirm graph representation and check if the graph is guaranteed to be a DAG.
Use DFS to find all paths, which is inefficient for large graphs.
Use Kahn's algorithm (BFS with in-degrees) or DFS with post-order traversal reversed. Kahn's algorithm easily handles level-by-level traversal.
Empty graph, disconnected graphs, graph with a cycle.
Tips
- What they are testing: Tested on cycle detection, disconnected components, and single-node graphs.
- Common mistake: Failing to check for cycles in graphs that are not guaranteed to be DAGs.
Related Flipkart questions
Collected from public candidate posts and coding forums. Updated Nov 2026.