Implement a deterministic topological ordering of a directed acyclic graph using DFS.
Given a directed graph with `n` nodes labeled `0` to `n-1` and an edge list `edges` where each edge is a tuple `(u, v)` representing a directed edge from `u` to `v`, write a function `topological_sort(n, edges)` that returns a list of all nodes in a topological order. For every edge `u -> v`, node `u` must appear before node `v` in the output. If the graph contains a cycle (including a self-loop), return `[]`.
The order must be deterministic and computed as follows:
1. Build an adjacency list where for each node, outgoing neighbors are recorded in the **same order** they appear in the edge list. Duplicate edges are ignored (they do not affect the order).
2. Perform DFS processing nodes in **increasing order** from `0` to `n-1`.
3. In the DFS, when visiting a node, explore its outgoing neighbors in **reverse order** of their appearance in the adjacency list (i.e., the neighbor that appears last in the edge list is visited first).
4. The result is the standard DFS finishing order reversed: after all descendants of a node are processed, append the node to a list, then reverse that list at the end.
This deterministic procedure guarantees a unique topological order for every DAG. You may use recursive or iterative DFS, but the order must follow the described neighbor iteration exactly.
Constraints
- `1 <= n <= 1000`
- `0 <= len(edges) <= 10000`
- Each edge is a tuple `(u, v)` with `0 <= u, v < n`.
- The graph may contain self-loops, duplicate edges, and cycles.
- Time complexity: O(n + E) where E is the number of distinct edges after ignoring duplicates.
- Space complexity: O(n + E) for the adjacency list and recursion stack.
Example
```python
# Example 1
n = 6
edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
result = topological_sort(n, edges)
# Expected: [5, 4, 2, 3, 1, 0]
# Example 2 (cycle)
n = 3
edges = [(0, 1), (1, 2), (2, 0)]
result = topological_sort(n, edges)
# Expected: []
# Example 3 (disconnected)
n = 5
edges = [(4, 1), (4, 0), (3, 2), (2, 1)]
result = topological_sort(n, edges)
# Expected: [3, 4, 2, 0, 1]
```
20 points
~25 min