Getting you started with the previously mentioned Tree module:

use Tree ();

my %nodes;

while (<>) {
   my ($child, $parent) = split /:/;

   my $parent_node = $nodes{$parent} ||= Tree->new($parent);
   my $child_node  = $nodes{$child}  ||= Tree->new($child);

   $parent_node->add_child($child_node);
}

my @roots = grep { $_->is_root } values %nodes;

die("Invalid data: No roots\n")
   unless @roots;

foreach (@roots) {
   ...
}
[download]

If you are only expecting one root, replace the bottom loop with:

die("Invalid data: Multiple roots\n")
   if @roots > 1;

my $root = $roots[0];

...
[download]

I didn't check for circular dependancies.