reconstruct a sequence from a set of partial order

Question

I have a set of elements pairs. Each one of theses pairs means : In the final sequence the first elements precedes the second element. The set of pairs contains enough pairs to reconstruct a unique sequence.

eg. :

If my set of pairs is {(A, B), (A, C), (C, B)}

= A precedes B, A precedes C and C precedes B.

my final sequence is ACB.

Now, I need an algorithm to reconstruct sequences from this kind of pair sets. Efficiency is critical. Any smart tip is welcome !

Answer 1

This is problem of Topological sorting of Oriented graph. Read More

Answer 2

Create a directed graph from those pairs, then perform topological sort.