OK, vagabonding electron, sorry that I misunderstood your requirement, I thought the chains were the input. This a quick (probably not optimal) way to do it with your actual source data:

use strict;
use warnings;
use Data::Dumper;

my %predec;

while (<DATA>) {
    chomp;
    my ($succ, $pred) = split /;/, $_;
    $pred = $succ if $pred eq '';
    push @{$predec{$pred}}, $succ;
}
my $continue = 1;
while ($continue) {
    $continue = 0;
    for my $pred (keys %predec) {
        my $succ = @{$predec{$pred}}[-1];    
        if (defined $succ and exists $predec{$succ} and scalar @{$pred
+ec{$succ}} != 0) {
            next if $succ eq $pred;
            push @{$predec{$pred}}, @{$predec{$succ}};
            delete $predec{$succ};
            $continue = 1;
        }
        $succ = @{$predec{$pred}}[0];
        if (defined $succ and exists $predec{$succ} and scalar @{$pred
+ec{$succ}} != 0) {
            unshift @{$predec{$pred}}, @{$predec{$succ}};
            delete $predec{$succ};
            $continue = 1;
        }
    }
}

print "Data structure: \n", Dumper \%predec;
print "\n\nResult:\n\n";

for my $key (keys %predec) {
    next if scalar @{$predec{$key}} == 0;
    print "$key => $key\n" and next if $key eq @{$predec{$key}}[0];
    print "$key => $key\n";
    print "$_ => $key\n" for @{$predec{$key}};
}

__DATA__
567;456
456;345
345;234
234;123
339;228
228;117
131;
435;324
324;213
372;
[download]

This will print the following:

$ perl  predecessor.pl
Data structure:
$VAR1 = {
          '123' => [
                     '234',
                     '345',
                     '456',
                     '567'
                   ],
          '131' => [
                     '131'
                   ],
          '234' => [],
          '213' => [
                     '324',
                     '435'
                   ],
          '345' => [],
          '324' => [],
          '372' => [
                     '372'
                   ],
          '117' => [
                     '228',
                     '339'
                   ]
        };


Result:

123 => 123
234 => 123
345 => 123
456 => 123
567 => 123
131 => 131
213 => 213
324 => 213
435 => 213
372 => 372
117 => 117
228 => 117
339 => 117
[download]

This seems to be what you want, except that the lines are not printed out in the same order as your example. If the order matters, it should be quite simple to sort the lines in the desired order.