Por Samyra Almeida
Para resolver esse problema é necessário conhecimento sobre o algoritmo de LCA(Menor Ancestral Comum).
Vamos tratar o mapa como uma árvore, onde os restaurantes são os nós e as estradas as arestas.
Com isso, para resolvermos as consultas do tipo 1, durante a DFS também vamos guardar um vetor dist[] = distância dos nós a raiz da árvore. Assim, a distância entre $$u$$ e $$v$$ é igual a $$dist[u] + dist[v] – 2*dist[LCA(u, v)]$$, onde $$dist[LCA(u, v)]$$ $$=$$ distância do $$LCA$$ de $$u$$ e $$v$$ a raiz da árvore, e como ela aparece duas vezes, tanto em $$dist[u]$$ como em $$dist[v]$$, também precisamos descontá-la duas vezes.
Agora para resolvermos a consulta do tipo 2, chamar a função $$find(u,$$ $$k)$$ que retorna o k-ésimo nó no caminho de $$u \rightarrow raiz$$. Para montarmos o algoritmo dessa função iremos utilizar a mesma tabela utilizada para descobrirmos o $$LCA$$ entre dois nós, como sabemos que o nó está $$k$$ níveis acima de $$u$$, basta irmos subindo $$u$$ até que encontremos o nó.
Mas antes de procurarmos o k-ésimo nó no caminho de $$u \rightarrow v$$, vamos analisar os três possíveis casos
- O k-ésimo nó é igual ao $$lca$$ entre $$u$$ e $$v$$: para checar esse caso, basta calcularmos a diferença entre os níveis de $$u$$ e o $$lca$$ e checamos e é igual a, se sim, imprimimos o $$lca$$ de $$u$$ e $$v$$, caso contrário, continuamos o algoritmo.
- O k-ésimo nó está antes do $$lca$$ entre $$u$$ e $$v$$: nesse caso basta chamarmos o $$find(u,$$ $$k – 1)$$ e imprimimos o nó que a função retornará.
- O k-ésimo nó está depois do $$lca$$ entre $$u$$ e $$v$$: chame de $$a$$ o k-ésimo nó no caminho entre $$u$$ e $$v$$, nesse caso, precisamos saber quantos nós $$a$$ está acima de $$v$$. Para isso basta calcularmos quantos nós existem no caminho de $$u$$ até $$v$$ e descontarmos $$k$$.
Segue código solução para maior compreensão:
https://gist.github.com/samyravitoria/b4bde957a3678612de0c7c6fef99c6c7
Deixe um comentário