O básico de conjuntos disjuntos
Passo 1 de 8
Seis elementos, cada um é seu próprio pai. São seis grupos separados, antes de qualquer união.
A ideia
Mantenha um array: parent[x] é para quem x aponta. Siga os ponteiros e você para em um elemento que aponta para si mesmo — a raiz, que é o nome do grupo.
find sobe até essa raiz. union encontra as duas raízes e pendura uma embaixo da outra, mesclando dois grupos com uma única escrita.
Exemplo do mundo real
Uma biblioteca de fotos que agrupa rostos. Quando você confirma que dois clusters são a mesma pessoa, ela não reetiqueta cada foto — aponta um cluster para o outro. Depois, perguntar “é a mesma pessoa?” só compara as duas etiquetas a que você chega.
O código
Sua vez
Preencha a lacuna.
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