Pular para o conteúdo

O básico de conjuntos disjuntos

Aula 1 de 4 · 5 min

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 2

Mini quiz

1 / 3

Como se reconhece a raiz de um grupo?