Question 1281

Appended Too Early

A DFS-based topological sort:

order = []
visited = [False] * n

def dfs(v):
    visited[v] = True
    order.append(v)
    for u in adj[v]:
        if not visited[u]:
            dfs(u)

for v in range(n):
    if not visited[v]:
        dfs(v)
print(*order)

On the DAG 0→1, 0→2, 1→3, 2→3 with adjacency lists in increasing order, it prints 0 1 3 2. What is wrong with that output?

A

The order is valid, but the code will crash with a recursion error the moment the input contains a cycle.

B

It puts 3 before 2, violating the edge 2→3. The append has to move below the loop, and the resulting list then has to be reversed.

C

Nothing. 0 1 3 2 is a valid order here; the bug only shows on a graph with more than one source vertex.

D

The order is right but backwards. Reversing it to 2 3 1 0 fixes it.