Pular para o conteúdo

Compressão de caminho

Aula 2 de 4 · 5 min

Compressão de caminho

Passo 1 de 10

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

Quando acontece a compressão de caminho?