Dependency order

Find a dependency order in a DAG.

Topological sorting orders nodes in a directed acyclic graph (DAG) by their dependencies. Each node comes after all nodes it depends on.

It is used wherever dependencies exist, like build tasks or course prerequisites. If a cycle exists, no order is possible.

Adjacency list

The graph is represented as an adjacency list of each node's successors. For example graph[0] = [1, 2] shows edges from 0 to 1 and 2.

This representation clearly expresses dependencies. Each node lists only the nodes that depend on it.

Write init_graph(). Return the adjacency list. Print it with print(init_graph()).

Show example solution

def init_graph():
    # Return adjacency list
    return [[1, 2], [3], [3], []]
print(init_graph())