Compressão de caminho
Passo 1 de 10
profundidade4saltos0
Uma cadeia: 0 aponta para 1, 1 para 2, até 4. Todo find precisa percorrer tudo de novo.
A ideia
As uniões podem montar uma cadeia longa, e aí cada find percorre tudo de novo. Mas o percurso já descobriu a resposta.
Então faça uma segunda passada pelo mesmo caminho e aponte cada nó direto para a raiz. O caminho que você pagou uma vez fica plano para todo mundo que usá-lo depois.
Exemplo do mundo real
Um atendimento telefônico que transfere você por três departamentos até chegar à única pessoa que pode ajudar. Na segunda vez, você liga direto para o número dela. Ninguém refaz a rota, porque valia a pena anotá-la.
O código
Sua vez
O que isto imprime?
parent = [1, 2, 2]
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root:
parent[x], x = root, parent[x]
return root
find(0)
print(parent)Mini quiz
1 / 3