medium +20 pts

Topological Sort via DFS

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

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build an adjacency list where each node's neighbors are stored in the order they appear in the edge list.
Use three states: 0=unvisited, 1=visiting, 2=done. If you encounter a node in state 1 during DFS, there is a cycle.
When iterating over a node's adjacency list, go in reversed order using `for neighbor in reversed(graph[node]):`.
Process start nodes in increasing order from 0 to n-1. Append node to a list after visiting all descendants, then reverse at the end.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.