fork(1) download
copy 
  1. import java.util.*;
  2. import java.util.concurrent.ArrayBlockingQueue;
  3.  
  4. class LCA_fila {
  5.  
  6. 	static class Node {
  7. 		List<Node> children = new ArrayList<Node>();
  8. 		Integer id;
  9. 		Node(Integer id) {
  10. 			this.id = id;
  11. 		}
  12. 		public String toString() {
  13. 			return id.toString();
  14. 		}
  15. 	}
  16.  
  17. 	public static void main (String[] args) throws java.lang.Exception {
  18.  
  19. 		//test data
  20. 		Node root = new Node(0);
  21. 		Node n1 = new Node(1);
  22. 		Node n2 = new Node(2);
  23. 		Node n3 = new Node(3);
  24. 		Node n1a = new Node(11);
  25. 		Node n1b = new Node(12);
  26. 		Node n3a = new Node(31);
  27. 		Node n3b = new Node(32);
  28. 		Node n3c = new Node(33);
  29.  
  30. 		//connections
  31. 		root.children.add(n1);
  32. 		root.children.add(n2);
  33. 		root.children.add(n3);
  34. 		n1.children.add(n1a);
  35. 		n1.children.add(n1b);
  36. 		n3.children.add(n3a);
  37. 		n3.children.add(n3b);
  38. 		n3.children.add(n3c);
  39.  
  40. 		//tests
  41. 		System.out.println("### Test 1 ###");
  42. 		Node r = findClosestCommonAncestor(root, n1b, n3a);
  43. 		System.out.println("Expected: " + root);
  44. 		System.out.println("Result: " + r);
  45. 		System.out.println("Passed --> " + (r == root));
  46.  
  47. 		System.out.println("### Test 2 ###");
  48. 		r = findClosestCommonAncestor(root, n3, n3b);
  49. 		System.out.println("Expected: " + n3);
  50. 		System.out.println("Result: " + r);
  51. 		System.out.println("Passed --> " + (r == n3));
  52.  
  53. 		System.out.println("### Test 3 ###");
  54. 		r = findClosestCommonAncestor(root, n3a, n3c);
  55. 		System.out.println("Expected: " + n3);
  56. 		System.out.println("Result: " + r);
  57. 		System.out.println("Passed --> " + (r == n3));
  58.  
  59. 		System.out.println("### Test 4 ###");
  60. 		r = findClosestCommonAncestor(root, n2, n1a);
  61. 		System.out.println("Expected: " + root);
  62. 		System.out.println("Result: " + r);
  63. 		System.out.println("Passed --> " + (r == root));
  64.  
  65. 	}
  66.  
  67.  
  68. 	static Node findClosestCommonAncestor(Node ancestralComum, Node p, Node q) {
  69.  
  70. 		Queue<Node> fila = new ArrayBlockingQueue<Node>(100);
  71.  
  72. 		while(true){
  73.  
  74. 			// Adicionar todos os filhos do ancestral comum obtido ate agora na fila
  75. 			fila.clear();
  76. 			for( Node e: ancestralComum.children ){
  77. 				fila.add(e);
  78. 				fila.add(e);
  79. 			}
  80.  
  81. 			// Vai passando os ancestrais ate descobrir os nodes e seus ancestrais
  82. 			Node p_ancestral=null, q_ancestral=null;
  83. 			while(p_ancestral == null || q_ancestral == null){
  84. 				Node e = fila.remove();
  85. 				Node a = fila.remove();
  86.  
  87. 				for( Node filho : e.children ){
  88. 					fila.add(filho);
  89. 					fila.add(a);
  90. 				}
  91.  
  92. 				if(e == p)
  93. 					p_ancestral = a;
  94. 				if(e == q)
  95. 					q_ancestral = a;	
  96. 			}
  97.  
  98. 			// Condicoes para termino ou continuacao do algoritmo
  99. 			if(p_ancestral == q_ancestral)
  100. 				ancestralComum = p_ancestral;
  101. 			else
  102. 				break;
  103. 			if(p == ancestralComum || q == ancestralComum)
  104. 				break;
  105. 		}
  106.  
  107. 		return ancestralComum;
  108. 	}
  109.  
  110. }
  111.  
Success #stdin #stdout 0.1s 321600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
### Test 1 ###
Expected: 0
Result: 0
Passed --> true
### Test 2 ###
Expected: 3
Result: 3
Passed --> true
### Test 3 ###
Expected: 3
Result: 3
Passed --> true
### Test 4 ###
Expected: 0
Result: 0
Passed --> true
https://ideone.com/8ZcIba
Resposta do Stack Overflow - Qual a versão iterativa do algoritmo LCA
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!