Topological Sort

Score: 87.57 (pass)

#!perl -lan0
sub f{$p{$_}||=1/!$g{$_}+++map(&f,$x=~/^(.*) (?!\1
)\Q$_
/mg)+print}$x=$_;f for@F

Score: 96.59 (pass)

#!perl -lan0
sub f{1/!$g{$_}++;$p{$_}||=map(&f,$x=~/^(.*) (?!\1
)\Q$_
/mg)+print;$g{$_}=0}$x=$_;f for@F

Score: 98.58 (pass)

#!perl -lan0
sub f{1/!$g{$_}++;$p{$_}++or map(&f,$x=~/^(.*) (?!\1
)\Q$_
/mg),print;$g{$_}=0}$x=$_;f for@F

Score: 103.51 (fail)

Nasty...

#!perl -lap0
@g{@F}=0;$x=$_}sub a{map{(1)x("@_"eq$_||a($_))}$x=~/(.*) \Q@_
/g,@_}for(sort{a($a)<=>a$b}keys%g){

Score: 108.56 (pass)

#!perl -lan0
sub f{$g{$_}++&&&g;$p{$_}++or map(&f,$x=~/(.*) \Q$_
/g),print;$g{$_}=0}s/^(.*) \1$/$1/mg;$x=$_;f for@F

Score: 110.50 (fail)

#!perl -lap0
@g{@F}=$x=$_}sub a{map{(1)x("@_"eq$_||a($_))}$x=~/(.*) \Q@_
/g,@_}alarm 20;for(sort{a($a)<=>a$b}keys%g){

Score: 113.54 (pass)

#!perl -lap0
$_ x=@F;s#(.*) (.*)#$g{$2}>($g{$1}x=1)||log@F-($g{$2}=$g{$1}+($1ne$2))#ge}for(sort{$g{$a}<=>$g{$b}}keys%g){

Score: 113.56 (pass)

Eureka!

#!perl -lan0
sub f{$g{$_}++&&&g;if(!$p{$_}++){&f for $x=~/(.*) \Q$_\E\n/g;print}$g{$_}=0}s/^(.*) \1$/$1/mg;$x=$_;f for@F

Score: 114.53 (pass)

#!perl -lap0
$_ x=@F;s#(.*) (.*)#$g{$2}>($g{$1}x=1)or@F>($g{$2}=$g{$1}+($1ne$2))or&f#ge}for(sort{$g{$a}<=>$g{$b}}keys%g){

Score: 114.54 (pass)

#!perl -lap0
$_ x=@F;s#(.*) (.*)#$g{$2}>($g{$1}x=1)or($g{$2}=$g{$1}+($1ne$2))<@F||&f#ge}for(sort{$g{$a}<=>$g{$b}}keys%g){

Score: 119.51 (pass)

As the refs didn't like my memory eating recursion trick, I've added a signal handler. This solution needs the -w.

#!perl -wlap0
$SIG{__WARN__}=[@g{@F}=$x=$_]}sub a{map{(1)x("@_"eq$_||a($_))}$x=~/(.*) \Q@_
/g,@_}for(sort{a($a)<=>a$b}keys%g){

Score: 121.55 (pass)

#!perl -lap0
@g{@F}=0;$_ x=@o=keys%g;s#(.*) (.*)#$g{$2}>$g{$1}or($g{$2}=$g{$1}+($1ne$2))<@o||&f#ge}for(sort{$g{$a}<=>$g{$b}}@o){

Score: 124.56 (pass)

#!perl -lap0
@g{@F}=a;$_ x=@o=keys%g;$2eq$1||$g{$2}>$g{$1}||a/(($g{$2}=$g{$1}+1)<@o)while/(.*) (.*)/g}for(sort{$g{$a}<=>$g{$b}}@o){

Score: 135.55 (fail)

Eureka!

#!perl -lap0
@g{@F}=0;$_ x=@F;$2eq$1or$g{$2}>$g{$1}or$g{$2}=$g{$1}+1while/(.*)
(.*)/g}1/!grep$g{$_}>@o,@o=keys%g;for(sort{$g{$a}<=>$g{$b}}@o){

Score: 145.56 (pass)

You don't often see a for(;;) loop in golf. It's slowly getting better, but I'll have to find a better algorithm.

#!perl -lan00
$g{$_}+=$|--for@F;$g{$_}--for/^(.*) \1$/gm;for($y=@o=keys%g;$y-=@n;){for$x(@n=grep!$g{$_},@o){$g{$_}--||print for/^\Q$x\E (.*)/gm,$x}1/@n}

Score: 148.56 (pass)

#!perl -lan00
$g{$_}+=$|--for@F;$g{$_}--for/^(.*) \1$/gm;for($y=@o=keys%g;$y-=@n;){1/(@n=grep!$g{$_},@o);for$x(@n){$g{$_}--||print for/^\Q$x\E (.*)/gm,$x}}

Score: 150.55 (pass)

#!perl -lan00
$g{$_}+=$|--for@F;$g{$_}--for/^(.*) \1$/gm;while(grep$g{$_}>=0,@F){1/(@n=grep!$g{$_},keys%g);for$x(@n){$g{$_}--||print for/^\Q$x\E (.*)/gm,$x}}

Score: 153.55 (pass)

Undefined subroutine &main::x called...

#!perl -lan00
$g{$_}+=$|--for@F;$g{$_}--for/^(.*) \1$/gm;while(grep$g{$_}>=0,@@=keys%g){@n=grep!$g{$_},@@or&x;for$x(@n){print$x;$g{$_}--for/^\Q$x\E (.*)/gm,$x}}

Score: 160.52 (pass)

Grrrr... ugly solution... much too long... can't see anything shorter... really don't like this course... grrrr.

#!perl -ln00
$g{$_}+=$|--for/\S+/g;$g{$_}--for/^(.*) \1$/gm;while(grep$g{$_}>=0,keys%g){@n=grep!$g{$_},keys%g or die;for$x(@n){print$x;$g{$_}--for/^\Q$x\E (.*)/gm,$x}}