PPractick

The problem

A university lists courses with prerequisite edges (u → v means u must be taken before v), and the planner needs an order in which to take all courses without breaking any prerequisite: a topological order of the DAG. The DFS way: a vertex finishes only after everything reachable from it has finished. So if you push each vertex onto a stack when its DFS finishes, reversing that finish order puts every vertex before all of its descendants.

Example: 6 vertices, edges 5→2, 5→0, 4→0, 4→1, 2→3, 3→1 → [5, 4, 2, 3, 1, 0].

Function signature

vector<int> topoSort(int V, const vector<vector<int>>& adj);  // adj describes a DAG

Test cases

Input (V, edges)	Output (DFS from 0, 1, 2, …)	Explanation
(6, [[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]])	[5, 4, 2, 3, 1, 0]
(4, [[3,0],[1,0],[2,0]])	[3, 2, 1, 0]	0 must come last
(5, [[0,1],[1,2],[2,3],[3,4]])	[0, 1, 2, 3, 4]	A chain has one order
(2, [[0,1]])	[0, 1]
(3, [])	[2, 1, 0]	Any order is valid

(Confirm: the input is a DAG; many orders are valid, and the one shown comes from starting DFS at 0, 1, 2, … in turn.)

How interviewers phrase it

• "Given a directed acyclic graph, return any topological ordering of its vertices" (GeeksforGeeks "Topological sort").

Clarifying questions to ask

1. Is the graph guaranteed acyclic? (Yes. Otherwise no order exists; detect that with the gray/black colouring.)
2. Any valid order accepted? (Yes.)
3. Disconnected parts? (Yes, so start DFS from every unvisited vertex.)

Follow-ups to expect

1. "Why reverse the finish order?"
2. "Why does it need a DAG?"
3. "BFS alternative?"
4. "Uses?"
5. "Complexity?"

Related questions

• Course Schedule I Hard
• Find eventual safe states Hard
• Shortest path in DAG Hard
• Detect a cycle in an undirected graph Hard
• Bipartite Graph (DFS) Hard
• Cycle Detection in Directed Graph (DFS) Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in