import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
class LCA_fila {
static class Node {
List<Node> children = new ArrayList<Node>();
this.id = id;
}
return id.toString();
}
}
//test data
Node root = new Node(0);
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n1a = new Node(11);
Node n1b = new Node(12);
Node n3a = new Node(31);
Node n3b = new Node(32);
Node n3c = new Node(33);
//connections
root.children.add(n1);
root.children.add(n2);
root.children.add(n3);
n1.children.add(n1a);
n1.children.add(n1b);
n3.children.add(n3a);
n3.children.add(n3b);
n3.children.add(n3c);
//tests
System.
out.
println("### Test 1 ###"); Node r = findClosestCommonAncestor(root, n1b, n3a);
System.
out.
println("Expected: " + root
); System.
out.
println("Result: " + r
); System.
out.
println("Passed --> " + (r
== root
));
System.
out.
println("### Test 2 ###"); r = findClosestCommonAncestor(root, n3, n3b);
System.
out.
println("Expected: " + n3
); System.
out.
println("Result: " + r
); System.
out.
println("Passed --> " + (r
== n3
));
System.
out.
println("### Test 3 ###"); r = findClosestCommonAncestor(root, n3a, n3c);
System.
out.
println("Expected: " + n3
); System.
out.
println("Result: " + r
); System.
out.
println("Passed --> " + (r
== n3
));
System.
out.
println("### Test 4 ###"); r = findClosestCommonAncestor(root, n2, n1a);
System.
out.
println("Expected: " + root
); System.
out.
println("Result: " + r
); System.
out.
println("Passed --> " + (r
== root
));
}
static Node findClosestCommonAncestor(Node ancestralComum, Node p, Node q) {
Queue<Node> fila = new ArrayBlockingQueue<Node>(100);
while(true){
// Adicionar todos os filhos do ancestral comum obtido ate agora na fila
fila.clear();
for( Node e: ancestralComum.children ){
fila.add(e);
fila.add(e);
}
// Vai passando os ancestrais ate descobrir os nodes e seus ancestrais
Node p_ancestral=null, q_ancestral=null;
while(p_ancestral == null || q_ancestral == null){
Node e = fila.remove();
Node a = fila.remove();
for( Node filho : e.children ){
fila.add(filho);
fila.add(a);
}
if(e == p)
p_ancestral = a;
if(e == q)
q_ancestral = a;
}
// Condicoes para termino ou continuacao do algoritmo
if(p_ancestral == q_ancestral)
ancestralComum = p_ancestral;
else
break;
if(p == ancestralComum || q == ancestralComum)
break;
}
return ancestralComum;
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS51dGlsLmNvbmN1cnJlbnQuQXJyYXlCbG9ja2luZ1F1ZXVlOwoKY2xhc3MgTENBX2ZpbGEgewoJCglzdGF0aWMgY2xhc3MgTm9kZSB7CgkJTGlzdDxOb2RlPiBjaGlsZHJlbiA9IG5ldyBBcnJheUxpc3Q8Tm9kZT4oKTsKCQlJbnRlZ2VyIGlkOwoJCU5vZGUoSW50ZWdlciBpZCkgewoJCQl0aGlzLmlkID0gaWQ7CgkJfQoJCXB1YmxpYyBTdHJpbmcgdG9TdHJpbmcoKSB7CgkJCXJldHVybiBpZC50b1N0cmluZygpOwoJCX0KCX0KCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24gewoJCQoJCS8vdGVzdCBkYXRhCgkJTm9kZSByb290ID0gbmV3IE5vZGUoMCk7CgkJTm9kZSBuMSA9IG5ldyBOb2RlKDEpOwoJCU5vZGUgbjIgPSBuZXcgTm9kZSgyKTsKCQlOb2RlIG4zID0gbmV3IE5vZGUoMyk7CgkJTm9kZSBuMWEgPSBuZXcgTm9kZSgxMSk7CgkJTm9kZSBuMWIgPSBuZXcgTm9kZSgxMik7CgkJTm9kZSBuM2EgPSBuZXcgTm9kZSgzMSk7CgkJTm9kZSBuM2IgPSBuZXcgTm9kZSgzMik7CgkJTm9kZSBuM2MgPSBuZXcgTm9kZSgzMyk7CgkJCgkJLy9jb25uZWN0aW9ucwoJCXJvb3QuY2hpbGRyZW4uYWRkKG4xKTsKCQlyb290LmNoaWxkcmVuLmFkZChuMik7CgkJcm9vdC5jaGlsZHJlbi5hZGQobjMpOwoJCW4xLmNoaWxkcmVuLmFkZChuMWEpOwoJCW4xLmNoaWxkcmVuLmFkZChuMWIpOwoJCW4zLmNoaWxkcmVuLmFkZChuM2EpOwoJCW4zLmNoaWxkcmVuLmFkZChuM2IpOwoJCW4zLmNoaWxkcmVuLmFkZChuM2MpOwoJCQoJCS8vdGVzdHMKCQlTeXN0ZW0ub3V0LnByaW50bG4oIiMjIyBUZXN0IDEgIyMjIik7CgkJTm9kZSByID0gZmluZENsb3Nlc3RDb21tb25BbmNlc3Rvcihyb290LCBuMWIsIG4zYSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJFeHBlY3RlZDogIiArIHJvb3QpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiUmVzdWx0OiAiICsgcik7CgkJU3lzdGVtLm91dC5wcmludGxuKCJQYXNzZWQgLS0+ICIgKyAociA9PSByb290KSk7CgkJCgkJU3lzdGVtLm91dC5wcmludGxuKCIjIyMgVGVzdCAyICMjIyIpOwoJCXIgPSBmaW5kQ2xvc2VzdENvbW1vbkFuY2VzdG9yKHJvb3QsIG4zLCBuM2IpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiRXhwZWN0ZWQ6ICIgKyBuMyk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJSZXN1bHQ6ICIgKyByKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlBhc3NlZCAtLT4gIiArIChyID09IG4zKSk7CgkJCgkJU3lzdGVtLm91dC5wcmludGxuKCIjIyMgVGVzdCAzICMjIyIpOwoJCXIgPSBmaW5kQ2xvc2VzdENvbW1vbkFuY2VzdG9yKHJvb3QsIG4zYSwgbjNjKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIkV4cGVjdGVkOiAiICsgbjMpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiUmVzdWx0OiAiICsgcik7CgkJU3lzdGVtLm91dC5wcmludGxuKCJQYXNzZWQgLS0+ICIgKyAociA9PSBuMykpOwoJCQoJCVN5c3RlbS5vdXQucHJpbnRsbigiIyMjIFRlc3QgNCAjIyMiKTsKCQlyID0gZmluZENsb3Nlc3RDb21tb25BbmNlc3Rvcihyb290LCBuMiwgbjFhKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIkV4cGVjdGVkOiAiICsgcm9vdCk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJSZXN1bHQ6ICIgKyByKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlBhc3NlZCAtLT4gIiArIChyID09IHJvb3QpKTsKCQkKCX0KCQoKCXN0YXRpYyBOb2RlIGZpbmRDbG9zZXN0Q29tbW9uQW5jZXN0b3IoTm9kZSBhbmNlc3RyYWxDb211bSwgTm9kZSBwLCBOb2RlIHEpIHsKCQkKCQlRdWV1ZTxOb2RlPiBmaWxhID0gbmV3IEFycmF5QmxvY2tpbmdRdWV1ZTxOb2RlPigxMDApOwoJCQoJCXdoaWxlKHRydWUpewoJCQkKCQkJLy8gQWRpY2lvbmFyIHRvZG9zIG9zIGZpbGhvcyBkbyBhbmNlc3RyYWwgY29tdW0gb2J0aWRvIGF0ZSBhZ29yYSBuYSBmaWxhCgkJCWZpbGEuY2xlYXIoKTsKCQkJZm9yKCBOb2RlIGU6IGFuY2VzdHJhbENvbXVtLmNoaWxkcmVuICl7CgkJCQlmaWxhLmFkZChlKTsKCQkJCWZpbGEuYWRkKGUpOwoJCQl9CgkKCQkJLy8gVmFpIHBhc3NhbmRvIG9zIGFuY2VzdHJhaXMgYXRlIGRlc2NvYnJpciBvcyBub2RlcyBlIHNldXMgYW5jZXN0cmFpcwoJCQlOb2RlIHBfYW5jZXN0cmFsPW51bGwsIHFfYW5jZXN0cmFsPW51bGw7CgkJCXdoaWxlKHBfYW5jZXN0cmFsID09IG51bGwgfHwgcV9hbmNlc3RyYWwgPT0gbnVsbCl7CgkJCQlOb2RlIGUgPSBmaWxhLnJlbW92ZSgpOwoJCQkJTm9kZSBhID0gZmlsYS5yZW1vdmUoKTsKCgkJCQlmb3IoIE5vZGUgZmlsaG8gOiBlLmNoaWxkcmVuICl7CgkJCQkJZmlsYS5hZGQoZmlsaG8pOwoJCQkJCWZpbGEuYWRkKGEpOwoJCQkJfQoKCQkJCWlmKGUgPT0gcCkKCQkJCQlwX2FuY2VzdHJhbCA9IGE7CgkJCQlpZihlID09IHEpCgkJCQkJcV9hbmNlc3RyYWwgPSBhOwkKCQkJfQoJCQoJCQkvLyBDb25kaWNvZXMgcGFyYSB0ZXJtaW5vIG91IGNvbnRpbnVhY2FvIGRvIGFsZ29yaXRtbwoJCQlpZihwX2FuY2VzdHJhbCA9PSBxX2FuY2VzdHJhbCkKCQkJCWFuY2VzdHJhbENvbXVtID0gcF9hbmNlc3RyYWw7CgkJCWVsc2UKCQkJCWJyZWFrOwoJCQlpZihwID09IGFuY2VzdHJhbENvbXVtIHx8IHEgPT0gYW5jZXN0cmFsQ29tdW0pCgkJCQlicmVhazsKCQl9CgkJCQoJCXJldHVybiBhbmNlc3RyYWxDb211bTsKCX0KCn0K