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