Does reversing the result of a topological sort on a graph where all edges are in the wrong direction result in a valid topological order, as if the edges were reversed before the sort?
a -> b
a -> c
b -> d
c -> d
could give a toposort of a b c d. Reversing this list gives d c b a. Reversing all edges in the graph before toposorting could also give d c b a. Is this true in the general case? I'm guessing no, but I can't find an example that fails.
It obviously is, if you look at it from the right angle.
After a topo-sort, if we store all nodes in a list, all arrows out from any edge point in the same direction. If we reverse the list, all arrows now point in the opposite direction. Since all arrows point the same way, it's a valid topological sort.
And the other approach, first flipping all edges and then performing a toposort obviously yields a valid toposort, or the toposort algorithm is broken.
The exact total order produced by the two approaches might differ, but they're both valid.