Given a directed acyclic graph (DAG) with n vertices and adjacency list adj, return a topological ordering using Kahn's algorithm. If the graph contains a cycle, return an error message.
Examples
Input: n = 3, adj = [[1], [2], []]
Output: [0, 1, 2]
Explanation: 0 -> 1 -> 2, so ordering is 0, 1, 2
Input: n = 4, adj = [[1, 2], [3], [3], []]
Output: [0, 2, 1, 3] or [0, 1, 2, 3]
Explanation: 0 must come before 1 and 2, both 1 and 2 must come before 3
Input: n = 3, adj = [[1], [2], [0]]
Output: "Cycle detected — Topological Sort not possible"
Explanation: Graph contains a cycle 0 -> 1 -> 2 -> 0
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ adj[i].length ≤ n - 1
- Graph may or may not be acyclic
Function Signature
function topologicalSortKahn(n, adj) {
// Your code here
}
Test Cases
- Basic cases: n=3, adj=[[1],[2],[]], n=4, adj=[[1,2],[3],[3],[]]
- Single node: n=1, adj=[[]]
- Disconnected graph: n=4, adj=[[1],[],[3],[]]
- Cycle detection: n=3, adj=[[1],[2],[0]], n=2, adj=[[1],[0]]
- Complex graph: n=5, adj=[[1,2],[3],[3,4],[],[]]
