Topological sort or Kahn's algorithm
Amazon
MicrosoftZZupeeThe problem
Given a Directed Acyclic Graph (DAG) with V vertices labeled from 0 to V-1.The graph is represented using an adjacency list where adj[i] lists all nodes connected to node. Find any Topological Sorting of that Graph.
In topological sorting, node u will always appear before node v if there is a directed edge from node u towards node v(u -> v).
The function should **return **an **array **representing the topological order. The output will be validated by our driver code, which checks the correctness of your topological sort. It will print **True **if the order is valid, otherwise False.
Input: V = 6,adj=[ [ ], [ ], [3], [1], [0,1], [0,2] ]
Output: [5, 4, 2, 3, 1, 0] Explanation: A graph may have multiple topological sortings.
- Node 5 must appear before 0 and 2
- Node 2 must appear before 3
- Node 3 must appear before 1
- Node 4 must appear before 0 and 1
One valid topological order is: [5, 4, 2, 3, 1, 0]
Input: V = 4, adj=[ [ ], [0], [0], [0] ]
Output: [3, 2, 1, 0] Explanation: The necessary conditions for the ordering are:
- Nodes 1, 2, and 3 must all appear before 0.
- Their internal order doesn’t matter.
One valid topological order is: [3, 2, 1, 0]
Input: V = 3, adj=[[1], [2], []]
- 1 ≤ V ≤ 10⁴
- 0 ≤ number of edges ≤ 10⁴
cpp
class Solution{
public:
vector<int> topoSort(int V, vector<int> adj[]){
}
};java
class Solution {
public int[] topoSort(int V, List<List<Integer>> adj) {
}
}python
class Solution:
def topoSort(self, V, adj):javascript
class Solution {
topoSort(V, adj) {
}
}csharp
class Solution
{
public List<int> TopoSort(int V, List<List<int>> adj)
{
}
}go
func topoSort(V int, adj [][]int) []int {
}Stuck? Show a way to structure it+
- 01Compute the indegree of every vertex from the adjacency list.
- 02Enqueue every zero-indegree vertex.
- 03Remove vertices, append them to the order, and release outgoing neighbors.
- 04Compare processed count with vertex count when cycle detection is required.
Reference answer
Then expect these follow-ups
How does processed count reveal a cycle?
Tests: cycle detection
How would DFS produce a topological order?
Tests: alternative method
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question