Question

Your job is to arrange n rambunctious 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 to put i somewhere behind j because

then i is capable of throwing something at j.

Give an algorithm that orders the line (or says it's not possible) in O(m + n) time.

Answer 1

Answer:-----------
Create a graph G in which each child is a vertex and every statement of the form “i hates j” results in a directed edge from i to j. Topologically sort the vertices. Use a modified topological sort that returns “false” or some other marker if the graph has a cycle (if the graph has a cycle, it’s not possible to line the children up safely). If the topological sort succeeds, line the children up according to the topological sort result.

Topological-Sort-Children(G)

1. select v ∈ G.V with no incoming edges
2. if v = nil and |G.V| ≠ 0
3. then return false
4. output v
5. G.V = G.V - v
6. Topological-Sort-Children(G)

The order of the output vertices (children) is the reverse order to put them in line; you can reverse the order in O(n) time (or you could have made edges from j to i instead of from i to j) Creating the graph takesO(n+m) time; running topological sort takes O(V+E) =O(m+n) time.