Solução Informática – Nivel Intermediário – Semana 27

Escrito por Leonardo Paes

Conhecimento prévio necessário:

• DFS

No enunciado do problema é dito que há somente um caminho entre quaisquer dois vértices. Teoricamente, grafos desse tipo são chamados de árvores. De modo prático, podemos usar deste fato para utilizarmos uma $DFS$ pouco modificada para solucionarmos nosso problema. Além do padrão, podemos utilizar como parâmetro para a função $DFS$ uma variável que guarde a distância percorrida para chegar no vértice atual $v$, partindo de certa raiz $u$, que basicamente nos diz a distância de $u$ pra $v$, justamente por só haver um caminho entre $u$ e $v$. Portanto, se utilizarmos o vértice $A$ do enunciado como a raiz da nossa $DFS$, saberemos a distância de $A$ pra $B$ assim que visitarmos o vértice $B$ na $DFS$.

Complexidade padrão da $DFS$ em uma árvore: $O(N)$. Confira o código abaixo para melhor entendimento: