Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/perl
- # Code assumes input graph is a binary tree as stated in
- # the problem, NOT a binary *search* tree. Requres log n
- # time and space, where n is the number of nodes in the tree.
- #
- # Example to compute LCA(3,6) in the tree in the diagram:
- # perl lca '8: 3 10; 3: 1 6; 6: 4 7; 10: 14; 14: 13' 3 6
- use strict;
- use warnings;
- my($rawtree, $node1, $node2) = @ARGV;
- print "LCA($node1, $node2) = ",
- LeastCommonAncestor(InvertGraph(ParseGraph($rawtree)), $node1, $node2);
- sub LeastCommonAncestor {
- my ($invertedtree, $node1, $node2) = @_;
- my %parentsofnode1 = map { $_ => 1 } Descendants($invertedtree, $node1);
- foreach my $parentofnode2 (Descendants($invertedtree, $node2)) {
- if ($parentsofnode1{$parentofnode2}) {
- return $parentofnode2;
- }
- }
- die "can't happen in a tree\n";
- }
- sub ParseGraph {
- my ($rawgraph) = @_;
- my %graph;
- foreach (split /\s*;\s*/, $rawgraph) {
- my ($node, $successors) = /^\s*([^:\s]*):\s*(.*)/;
- $node =~ s/^\s+//;
- $graph{$node} = { map { $_ => 1 } split /\s+/, $successors };
- }
- return \%graph;
- }
- sub InvertGraph {
- my ($graph) = @_;
- my %invertedgraph;
- foreach my $src (keys %$graph) {
- foreach my $dst (keys %{ $graph->{$src} }) {
- $invertedgraph{$dst}{$src} = 1;
- }
- }
- return \%invertedgraph;
- }
- sub Descendants {
- my ($dag, $node) = @_;
- return (
- $node,
- map { Descendants($dag, $_) } Successors($dag, $node),
- );
- }
- sub Successors {
- my ($graph, $node) = @_;
- return keys %{ $graph->{$node} };
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement