Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!

# Untitled

By: a guest on Mar 13th, 2011  |  syntax: None  |  size: 1.55 KB  |  views: 80  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #!/usr/bin/perl
2.
3. #  Code assumes input graph is a binary tree as stated in
4. #  the problem, NOT a binary *search* tree. Requres log n
5. #  time and space, where n is the number of nodes in the tree.
6. #
7. #  Example to compute LCA(3,6) in the tree in the diagram:
8. #  perl lca '8: 3 10; 3: 1 6; 6: 4 7; 10: 14; 14: 13' 3 6
9.
10. use strict;
11. use warnings;
12.
13. my(\$rawtree, \$node1, \$node2) = @ARGV;
14.
15. print "LCA(\$node1, \$node2) = ",
16.   LeastCommonAncestor(InvertGraph(ParseGraph(\$rawtree)), \$node1, \$node2);
17.
18. sub LeastCommonAncestor {
19.   my (\$invertedtree, \$node1, \$node2) = @_;
20.
21.   my %parentsofnode1 = map { \$_ => 1 } Descendants(\$invertedtree, \$node1);
22.
23.   foreach my \$parentofnode2 (Descendants(\$invertedtree, \$node2)) {
24.     if (\$parentsofnode1{\$parentofnode2}) {
25.       return \$parentofnode2;
26.     }
27.   }
28.   die "can't happen in a tree\n";
29. }
30.
31.
32. sub ParseGraph {
33.   my (\$rawgraph) = @_;
34.   my %graph;
35.   foreach (split /\s*;\s*/, \$rawgraph) {
36.     my (\$node, \$successors) = /^\s*([^:\s]*):\s*(.*)/;
37.     \$node =~ s/^\s+//;
38.     \$graph{\$node} = { map { \$_ => 1 } split /\s+/, \$successors };
39.   }
40.   return \%graph;
41. }
42.
43. sub InvertGraph {
44.   my (\$graph) = @_;
45.   my %invertedgraph;
46.   foreach my \$src (keys %\$graph) {
47.     foreach my \$dst (keys %{ \$graph->{\$src} }) {
48.       \$invertedgraph{\$dst}{\$src} = 1;
49.     }
50.   }
51.   return \%invertedgraph;
52. }
53.
54. sub Descendants {
55.   my (\$dag, \$node) = @_;
56.
57.   return (
58.     \$node,
59.     map { Descendants(\$dag, \$_) } Successors(\$dag, \$node),
60.   );
61. }
62.
63.
64. sub Successors {
65.   my (\$graph, \$node) = @_;
66.
67.   return keys %{ \$graph->{\$node} };
68. }
clone this paste RAW Paste Data
Top