use Graph::Directed;

my @array1 = qw(dog rat rat mouse);
my @array2 = qw(dog rat mouse bird);
my @array3 = qw(cat rat fish mouse);

my @elements;
push(@elements, \@array1, \@array2, \@array3);

my $graph = Graph::Directed->new;
for (0..$#elements) {
   # Check for duplicate GUIDs in this set
   my %seen = ();
   my @dup = ();
   foreach my $item (@{$elements[$_]}) {
      if ($seen{$item}++) {
         push(@dup, $item);
      }
   }
        
   unless ($#dup == -1) {
      print "Duplicate elements: @dup";
      exit;
   }

   # If all's well, add to the path
   $graph->add_path(@{$elements[$_]});
}

my @elements_ordered = $graph->toposort;

print "@elements_ordered\n";
[download]