Teoria dos conjuntos

Dentro da matemática temos os Sets, equivalente a conjuntos na teoria de conjuntos.

Também é um tipo de Python que você pode fazer para comprimir uma lista.

# Exemplo em Python
my_list = [1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,]
print(set(my_list))
# {1, 2, 3}

O que são Disjoint-Sets

E dentro dessa teoria, temos conjuntos disjuntos quando não tem elementos em comum entre eles.

Em SQL, ao fazer joins entre tabelas, podemos pensar em sets: um inner join retorna elementos comuns, e se duas tabelas forem disjuntas (não têm elementos em comum) o join retorna vazio.

Disjoint-Sets trabalham com a mesma ideia de verificar se conjuntos têm ou não interseção.

Em realidade, este é uma das melhores estruturas de dados para otimizar algoritmos em grafos.

Dentro dele suportamos duas operações:

• Union: Mesclando dois conjuntos em um único conjunto.
• Find : Encontrando um representante de um conjunto disjunto.

Exemplo de uso em grafos

Imagine a situação de uma rede social com diversas pessoas e você tem as seguintes tarefas a serem executadas:

• Adicione uma nova relação de amizade, ou seja, uma pessoa x se torna amiga de y adicionando um novo elemento a um conjunto.

• Descobrir se o indivíduo x é amigo do indivíduo y (amigo direto ou indireto)

Exemplo

Exemplo tirado do Geeks For Geeks

Recebemos 10 indivíduos, digamos, a,b,c,d,e,f,g,h,i,j

A seguir estão as relações a serem adicionadas:

a <-> b
b <-> d
c <-> f
c <-> i
j <-> e
g <-> j

Dadas perguntas como se a é amigo de d ou não.

Basicamente, precisamos criar os seguintes 4 grupos e manter uma conexão rapidamente acessível entre os itens do grupo:

G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e, g, j}
G4 = {h}

Caso fomos implementar o UnionFind

class UnionFind
  def initialize(size)
    # Inicializa cada elemento como seu próprio representante (pai)
    @parent = Array.new(size) { |i| i }
    # Rank ajuda a manter as árvores balanceadas
    @rank = Array.new(size, 0)
  end

  def find(i)
    # Aplica compressão de caminho
    if @parent[i] != i
      @parent[i] = find(@parent[i])
    end
    @parent[i]
  end

  def unite(i, j)
    irep = find(i)
    jrep = find(j)

    return if irep == jrep

    # União por rank
    if @rank[irep] < @rank[jrep]
      @parent[irep] = jrep
    elsif @rank[irep] > @rank[jrep]
      @parent[jrep] = irep
    else
      @parent[jrep] = irep
      @rank[irep] += 1
    end
  end
end

names = %w[a b c d e f g h i j]
name_to_index = names.each_with_index.to_h

uf = UnionFind.new(names.size)

relations = [["a", "b"], ["b", "d"], ["c", "f"], ["c", "i"], ["j", "e"], ["g", "j"]]
relations.each do |x, y|
  uf.unite(name_to_index[x], name_to_index[y])
end

x, y = "a", "d"
if uf.find(name_to_index[x]) == uf.find(name_to_index[y])
  puts "#{x} e #{y} são amigos (diretos ou indiretos)"
else
  puts "#{x} e #{y} não são amigos"
end

Onde usar o Disjoint-Set

Disjoint-Set é útil para a maioria dos problemas não triviais da computação muito provavelmente um problema em baixo nível pode ser resolvido com ele.

Exemplos de Alto Nível

Qualquer grande E-Commerce, empresa, sistema que for mexer com grafos pode usar o Disjoint-Set para otimizar em algumas especifidades.

Grafos

• Podemos usar o Disjoint-Set no Algoritmo de Kruskal para encontrar uma árvore geradora mínima.

• Podemos usar o Disjoint-Set para detectar Cíclos em grafos não direcionados.

• Podemos usar o Disjoint-Set para a identificação de componentes conectados.

Simulação

• Controle de conjuntos de objetos que se fundem e se dividem dinamicamente.

• Simulação de percolação ou clusters.

Exemplos de Baixo Nível

Qualquer coisa mais escondida sendo dentro de linguagens de programação, sistemas operacionais, bibliotecas … etc.

Problemas de Equivalência

• Manter classes de equivalência.

• Agrupamento por atributos compartilhados.

E no geral?

Se tiver muito no seu código questões do tipo “X e Y são relacionados?” em um conjunto dinâmico de relações, então Disjoint-Set é a escolha mais eficiente.

Conclusão

A estrutura Disjoint-Set (Union-Find) resolve com eficiência problemas baseados em conectividade dinâmica.

Com Union e Find, é possível gerenciar grupos, detectar relações e otimizar algoritmos em grafos com complexidade quase constante.

Se o problema envolve:

• Particionar elementos
• Verificar conexões
• Unir componentes rapidamente

Então Union-Find é a estrutura certa.

Simples, rápida e usada desde sistemas reais até algoritmos clássicos.