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 2Mini quiz
1 / 3