For a directed acrylic graph (DAG), topological sort creates a total order out of a partial order, i.e., it provides a viable serialisation of the events. A valid topological sort is only output for a valid DAG (invalid: if a cyclic graph).
This is done by running depth-first search, and outputting in decreasing finish time. It yields a time complexity of , since DFS has that time complexity, and we take time to insert to the front of the linked list.
In practice, for an undirected graph, we can still run topo sort — we can create directed edges, and when running DFS we can remove the back edges
for exams: be comfortable with producing topological ordering of graph + DFS + BFS