Your job is to arrange n ill-behaved children in a straight line, facing front. You are given a list of m statements of the form “i hates j”. If i hates j, then you do not want put i somewhere behind j, because then i is capable of throwing something at j.Above problem can be solved by modeling above problem as direct graph where a directed edge exists between two children i and j if i hates j. Doing a Topological sort on this graph is going to give us the answer. Here is how Topological sort works:
- Do a DFS on above graph.
- Associate "finishing time" with each node while doing DFS.
- Return the nodes in the decreasing order of "finishing time"
