# Untitled

a guest
Mar 13th, 2011
179
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }