Topological Sort (BFS)

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],[],[]]