← Volver a los ejercicios

El bosque, operación por operación

Ocho elementos, un make_set para cada uno y después siete uniones. El número que acompaña a cada línea es el de su archivo y el contador dice cuántas veces se ejecuta.

1. Antes de arrancar

Las uniones, en este orden: .

El rango de la raíz que queda al final sube, en total, cuántas veces.

2. Ejecute el código

Paso 0 de 0
En curso
Llamadas abiertas
Operaciones

3. El bosque

La flecha va del hijo al padre. Verde: raíz, con su rango encima. Ámbar: lo que find_set está mirando. Azul: la flecha que la línea 15 acaba de mover.

4. Los dos arreglos

Rangos sobre 0

5. Y ahora find_set(7)

Sobre el árbol que quedó, antes de mirar: por dónde sube la llamada y qué casillas de p deja distintas.

6. Para llevarse

Corra la misma secuencia cambiando union(8, 1) por union(1, 8) y diga qué casillas de p quedan distintas. Después encuentre una unión de la secuencia que se pueda mover de sitio sin que el bosque final cambie.