You want to implement some kind of topological sort.

Every time an item A occurs before an item B in one of your sublists, that is a constraint that A must occur before B in the global list. So add the edge A->B to your graph.

Now, you can do several things to your graph. If it has a cycle, you can give an error. Otherwise you can perform a topological sort using your favorite algorithm or graph library. This gives an ordering of the vertices that is consistent with the meaning of each of these A->B constraints.

If you want to know if there is more than one topological sort possible, you can do something similar to what I outlined here. Just rank the vertices in the same way as I described. Suppose there are N vertices in your graph. If at the end of this process you have N ranks, then there's only one topological ordering possible. Otherwise, some rank must have more than one vertex, and the graph has more than one valid topological ordering.

It looks like Graph.pm does everything you need except for testing for multiple topological sorts. But along with the simple algorithm I outlined for that, you should be pointed in the right direction.

Update: It just occured to me that my "ranking" procedure in fact gives a topological sort (indirectly). Just list the things in order of rank. Within ranks, you can assign the order arbitrarily. If there's a cycle, you will fail in the first step (finding rank-0 nodes).