Disjoin Set Union

Uma primitiva muito recorrente em concursos é saber dinamicamente quais elementos estão ligados num certo conjunto. Imaginem o seguinte problema: temos inicialmente $N$ conjuntos, cada um com um elemento de 1 a $N$. Agora temos de suportar duas operações:

1. Juntar o conjunto que contém o elemento $a$ com o conjunto que contém o elemento $b$;
2. Perguntar se o elemento $a$ e $b$ estão no mesmo conjunto?

Se já estudaram grafos, verão que esta situação aparece quando tentamos resolver o problema de árvores de suporte de custo mínimo, mas isso fica para depois.

A pergunta mantém-se, como resolver este problema? Vamos estudar um conjunto de estruturas de dados que podem ser aplicadas neste problema, culminando no estudo de union-find, a estrutura de dados mais eficiente para este problema.

Notem que esta estrutura é bastante versátil, podemos manter vários valores sobre os conjuntos representados. O rank, visto no artigo, representa a "profundidade" da árvore de hierarquia de conjuntos, mas podemos de forma semelhante manter o tamanho do conjunto, o valor máximo/mínimo do conjunto, ... Tudo o que consiga ser unido (merged) pode ser mantido.

Se ainda tiverem dúvidas e quiserem uma discussão mais visual, vejam o próximo artigo:

Aplicações

Vamos ver apenas um problema para aplicarmos o que aprendemos. Este problema não é muito fácil, mas é bastante instrutivo. Pensem em como usar informações sobre os conjuntos de forma útil e em como dar a volta ao facto de estarmos a separar e não a unir conjuntos.

* Link/cut trees

Podem estar a perguntar-se o seguinte: "e se eu quiser unir e separar conjuntos, como faço?". Bom, este problema é bastante mais complicado do que a sua versão mais simples (enfase no bastante). Uma solução possível conhecida passa por aplicar uma estrutura de dados chamada link/cut tree. Porém, não aconselhamos a que percam muito tempo, para já, com esta estrutura. O seu uso em concursos é muito raro, mas os conceitos que aplica são extremente interessantes.