Union-Find
📚 Introdução
Um jeito muito eficiente de trabalharmos com união de conjuntos disjuntos (sem elementos pertencentes aos dois ao mesmo tempo, que é o que ocorre na maioria dos casos) é o algoritmo Union-Find.
A ideia é muito simples: vamos juntar elementos como "membros de uma mesma família" e escolher um "patriarca" para cada família.
Cada elemento terá seu elemento "pai", e aquele que não tem (que é pai de si mesmo), é o patriarca da família.
Olhar se dois elementos estão na mesma família é muito simples, basta verificar se eles têm o mesmo patriarca!
Suponha que o pai de cada elemento (identificado por um número de 1 a n) está salvo no dicionário pai, onde pai[i] guarda o número do elemento que é o pai do elemento i.
Desse modo, para encontrar o patriarca de i, basta olharmos seus ancestrais um a um até encontrarmos um patriarca (alguém que é pai de si mesmo).
Note que na figura acima há 5 elementos identificados por números de 1 a 5. Eles estão divididos em duas famílias, cujos patriarcas são 1 e 4.
E para unir dois elementos? Toda vez que dizemos que dois elementos quaisquer estão na mesma família, devemos fazer a união de todos os elementos das duas famílias em um conjunto só, ou seja: devemos associar o mesmo patriarca a todos eles. Para isso, basta que façamos o patriarca de uma família ser o pai do patriarca da outra, assim todos os descendentes do ex-patriarca agora serão descendentes do novo patriarca de todo o conjunto!
📝 Implementação
Em python, podemos implementar o Union-Find da seguinte forma:
pai = {i: i for i in range(1, n + 1)} # inicialmente, cada elemento é pai de si mesmo
def find(x):
# se x é pai de si mesmo, ele é o patriarca
if pai[x] == x:
return x
# caso contrário, x não é o patriarca, então vamos procurar o patriarca de seu pai
return find(pai[x])
def join(x, y):
pai[find(x)] = find(y) # o patriarca de x passa a ser o patriarca de yA função find é a responsável por encontrar o patriarca de um elemento, e a função join é a responsável por juntar dois elementos em uma mesma família.
Essa implementação é muito simples e eficiente, mas não é a mais eficiente possível. Para melhorar a eficiência, podemos usar uma técnica chamada compressão de caminhos.
📐 Otimizações
A compressão de caminhos é uma técnica que consiste em fazer com que todos os elementos de uma família apontem diretamente para o patriarca, ao invés de apontarem para o pai de seu pai, que aponta para o pai de seu pai, e assim por diante.
Assim diminuimos o tempo de execução da função find, pois não precisamos mais percorrer todos os ancestrais de um elemento para encontrar seu patriarca.
O código fica assim:
pai = {i: i for i in range(1, n + 1)} # inicialmente, cada elemento é pai de si mesmo
def find(x):
# se x é pai de si mesmo, ele é o patriarca
if x != pai[x]:
pai[x] = find(pai[x])
return pai[x]
def join(x, y):
pai[find(x)] = find(y) # o patriarca de x passa a ser o patriarca de yNote que a função find agora é recursiva, e a compressão de caminhos só é feita quando o elemento não é o patriarca.
Ainda podemos fazer mais uma mudança para melhorar a eficiência: vamos fazer com que o patriarca de uma família seja aquele que tem mais elementos.
Com essas mudanças as famílias ficam mais "equilibradas", e evitamos ter famílias muito grandes e outras muito pequenas, o que poderia prejudicar a eficiência do Union-Find.
pai = {i: i for i in range(1, n + 1)} # inicialmente, cada elemento é pai de si mesmo
peso = {i: 0 for i in range(1, n + 1)} # inicialmente, cada família tem peso 0
def find(x):
# se x é pai de si mesmo, ele é o patriarca
if x != pai[x]:
pai[x] = find(pai[x])
return pai[x]
def join(x, y):
x = find(x)
y = find(y)
# se x e y já estão na mesma família, não precisamos fazer nada
if x == y:
return
# se x e y não estão na mesma família, vamos juntar as duas
# fazendo com que o patriarca da maior família seja o pai do patriarca da menor família
if peso[x] < peso[y]:
pai[x] = y
if peso[x] > peso[y]:
pai[y] = x
if peso[x] == peso[y]:
pai[x] = y
peso[y] += 1Essa implementação do Union-Find com suas duas funções bem otimizadas é mágica! Você pode considerar que ambas têm complexidade apenas de O(1) e fazer tranquila e eficientemente todos os problemas que precisar.
🧑🏫 Exercícios
Last updated