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