Saltar al contenido

Compresión de caminos

Lección 2 de 4 · 5 min

Compresión de caminos

Paso 1 de 10

Una cadena: 0 apunta a 1, 1 a 2, hasta 4. Cada find tiene que recorrerla entera otra vez.

La idea

Las uniones pueden formar una cadena larga, y entonces cada find la vuelve a recorrer. Pero ese recorrido ya encontró la respuesta.

Así que haz una segunda pasada por el mismo camino y apunta cada nodo directo a la raíz. El camino que pagaste una vez queda plano para todos los que lo usen después.

Ejemplo del mundo real

Un menú telefónico te transfiere por tres departamentos antes de llegar a la única persona que puede ayudarte. La segunda vez, llamas a su número directo. Nadie vuelve a deducir el recorrido, porque valía la pena anotarlo.

El código

Te toca

¿Qué imprime esto?

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

¿Cuándo ocurre la compresión de caminos?