For directed acyclic graphs, a topological sort of a directed graph is such that if there’s an edge A \to B, then A comes before B in the sort (i.e. there’s not an edge from B to A). Under direct acyclic graphs, a topological sort always exist. solving topological sort with depth first search In a DAG, you can always go from larger finish times to smaller finish times in depth first search to be able to get a topological sort. Case 1: B is a descendant of A in the DFS tree. Then B finish time would be earlier than A finish time. Then A would be sorted first. Case 2: A is a descendant of A. Then, we must have explored B before A (otherwise if we explored A first we would have gotten to B and hence it would be children). And so B finish time is earlier than A finish chem. Case 3: neither is a descendant (its not connected): then one component will start and finish fully before another, this makes topo sort ordering not mater.