Following Orders (experts only)
Time Limit: 9000 ms Memory Limit: 10000 KiB
Order is an important concept in mathematics and in computer
science. For example, Zorn's Lemma states: ``a partially ordered
set in which every chain has an upper bound contains a maximal
element.'' Order is also important in reasoning about the fix-point
semantics of programs.
This problem involves neither Zorn's Lemma nor fix-point
semantics, but does involve order.
Given a list of variable constraints of the form x < y, you are to
write a program that prints all orderings of the variables that are
consistent with the constraints.
For example, given the constraints x < y and x < z there are two
orderings of the variables x, y, and z that are consistent with
these constraints: x y z and x z y.
The input consists of a sequence of constraint specifications. A
specification consists of two lines: a list of variables on one
line followed by a list of contraints on the next line. A
constraint is given by a pair of variables, where x y indicates that
x < y.
All variables are single character, lower-case letters. There
will be at least two variables, and no more than 20 variables in a
specification. There will be at least one constraint, and no more
than 50 constraints in a specification. There will be at least one,
and no more than 300 orderings consistent with the contraints in a
Input is terminated by end-of-file.
For each constraint specification, all orderings consistent with
the constraints should be printed. Orderings are printed in
lexicographical (alphabetical) order, one per line. Characters on a
line are separated by whitespace.
Output for different constraint specifications is separated by a
a b f g a b b f v w x y z v y x v z v w v
abfg abgf agbf gabf wxzvy wzxvy xwzvy xzwvy zwxvy zxwvy