Saltar al contenido

Fundamentos de conjuntos disjuntos

Lección 1 de 4 · 5 min

Fundamentos de conjuntos disjuntos

Paso 1 de 8

Seis elementos, cada uno es su propio padre. Son seis grupos separados, antes de unir nada.

La idea

Mantén un solo array (arreglo): parent[x] es a quién apunta x. Sigue los punteros y te detendrás en un elemento que se apunta a sí mismo: la raíz, que es el nombre del grupo.

find sube hasta esa raíz. union encuentra ambas raíces y cuelga una debajo de la otra, fusionando dos grupos con una sola escritura.

Ejemplo del mundo real

Una biblioteca de fotos que agrupa rostros. Cuando confirmas que dos grupos son la misma persona, no vuelve a etiquetar cada foto: hace que un grupo apunte al otro. Después, preguntar “¿es la misma persona?” solo compara las dos etiquetas a las que llegas.

El código

Te toca

Completa el espacio en blanco.

parent = [0, 0, 2, 2]
def find(x):
  while parent[x] ___ x:
      x = parent[x]
  return x
print(find(1), find(3))   # 0 2

Mini quiz

1 / 3

¿Cómo se reconoce la raíz de un grupo?