Topological Sort (DFS)

Given a directed acyclic graph (DAG) with n vertices and adjacency list adj, return any topological ordering of the vertices.

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 = 1, adj = [[]]
Output: [0]
Explanation: Single node graph

Constraints

• 1 ≤ n ≤ 10^4
• 0 ≤ adj[i].length ≤ n - 1
• The graph is a directed acyclic graph (DAG)
• There are no self-loops or multiple edges

Function Signature

function topologicalSort(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],[]]
• Complex graph: n=4, adj=[[1,2],[3],[3],[]]
• Empty graph: n=3, adj=[[],[],[]]