Solução Túneis Subterrâneos

0 Flares Facebook 0 0 Flares ×

Solução por Lucca Siaudzionis

Este problema é um problema básico se for resolvido pelo algoritmo do Mínimo Ancestral Comum (LCA - Lowest Common Ancestor). Há duas maneiras típicas de fazer, uma em O(n \ lg n) e outra em O(n \ \sqrt{n} ). Você pode aprender a fazer o o LCA em O(n \ \log{n}) na nossa aula do Curso Noic de Informática, clicando aqui. Além disso, um material que explica (em português!) muito bem o LCA em O(n \ \sqrt{n}) pode ser visto neste link.

Seguindo o mesmo estilo que se faz no material, o código fica assim:

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: