Escrito por Lúcio Figueiredo e Thiago Mota
Conhecimento prévio necessário:
O Union Find é bastante usado em diversos problemas relacionados a grafos ou conjuntos. Nesta Ideia, vamos demonstrar algumas aplicações interessantes desta estrutura de dados.
Union Find “De trás para frente”
A motivação segue do seguinte problema: É dado um grafo com $$N$$ vértices e $$M$$ arestas, além de $$Q$$ operações. Em cada operação, uma aresta será removida do grafo. Após cada umas das $$Q$$ operações, imprima a quantidade de componentes conexas presentes no grafo.
Perceba que esse problema é o oposto da aplicação clássica do Union Find – ao invés de adicionar arestas, estamos removendo-as. Como remover arestas de um grafo não parece ser uma tarefa fácil, podemos tentar imaginar o contrário, ou seja, pensar no problema de de trás para frente.
Imagine que vamos começar com o grafo resultante após todas as $$Q$$ arestas serem removidas. A quantidade de componentes conexas neste grafo já nos dá a resposta para a $$Q$$-ésima operação. Adicionando a última aresta removida (de índice $$Q$$) neste grafo final, o grafo resultante será o mesmo obtido ao remover as $$Q-1$$ primeiras arestas. Perceba, então, que podemos adicionar as arestas que foram removidas em ordem contrária, partindo do grafo final. Desta maneira, teremos a resposta para todas as operações. No entanto, como estamos obtendo-as em uma ordem diferente da ordem pedida no problema, teremos que guardar as respostas e imprimi-las depois de processar todas elas – podemos fazer isso utilizando um vetor com $$Q$$ posições, onde a $$i$$-ésima posição guarda a resposta após a $$i$$-ésima operação.
Assim, o problema foi reduzido para a aplicação comum do Union Find: adicionar arestas a um grafo e computar a quantidade de componentes conexas presentes neste grafo. A complexidade final será $$O(Q \cdot \alpha(n))$$, onde $$O(\alpha(n))$$ é a complexidade de cada operação do UF. Confira o código abaixo para melhor entendimento:
Em geral, ao lidar com operações aparentemente complicadas em um problema, é uma boa ideia imaginar cada uma delas ao contrário, com o objetivo de simplificá-las.
Small to Large
Imagine o seguinte problema geral: Possuímos diversos conjuntos (como um set do C++) e realizamos várias operações que consistem em unir dois conjuntos quaisquer em um só. Se o total de elementos nos conjuntos é $$N$$, a quantidade de operações é $$Q$$, e a complexidade de unir conjuntos é $$O \big (f(N) \big )$$ (por exemplo, com um set do C++, $$f(n) = \log n$$), uma possível solução simples para o problema teria complexidade $$O(N \cdot f(N) \cdot Q)$$.
Iremos realizar a seguinte modificação nas operações: ao juntar dois conjuntos $$S_1$$ e $$S_2$$, onde $$|S_1| \leq |S_2|$$, sempre vamos inserir os elementos de $$S_1$$ em $$S_2$$. Ou seja, em cada operação, vamos iterar apenas pelos elementos de $$S_1$$ e inseri-los em $$S_2$$. Vamos, então, observar o que acontece com cada elemento do menor conjunto, $$S_1$$. Definindo $$T(a)$$ como o tamanho do conjunto ao qual o elemento $$a$$ pertence, é possível notar que para todo elemento $$a \in S_1$$, ao ser inserido em $$S_2$$, o seu novo valor $$T(a)$$ irá, no mínimo, duplicar, já que $$T(a) = |S_2| + |S_1| \geq 2 \cdot |S_1|$$.
Seja $$C(i)$$ a quantidade de vezes que o elemento $$i$$ fez parte do menor conjunto de uma operação. Note que a complexidade do algoritmo é igual à soma do tamanho do menor conjunto em cada uma das $$Q$$ operações, multiplicado for $$f(N)$$. Pórem, isto é análogo à $$f(N)$$ vezes a soma de $$C(i)$$ para cada $$1 \leq i \leq N$$. Como citado anteriormente, em cada operação, o tamanho do conjunto resultante será maior ou igual ao dobro do tamanho do menor conjunto. Logo, teremos que $$C(i) \leq \log_2 N$$, pois como $$T(i)$$ é sempre menor ou igual a $$N$$, poderemos duplicar o tamanho do conjunto de $$i$$ no máximo $$\log_2 N$$ vezes. Assim, a complexidade final será igual a $$O \big(f(N) \cdot \sum\limits_{i=1}^{N} C(i) \big ) = O(N \cdot \log N \cdot f(N))$$.
Está técnica de sempre inserir o menor conjunto dentro do maior conjunto é conhecida como Small to Large e possui diversas aplicações. Uma delas é com o próprio Union Find. Imagine que estamos realizando as funções $$Find(x)$$ e $$Join(x, y)$$ sem nenhuma otimização. Se utilizarmos a técnica demonstrada anteriormente na função $$Join$$, ou seja, sempre definirmos o pai do conjunto resultante como o pai do maior conjunto, o Union Find possuirá complexidade amortizada de $$O(\log N)$$, pelo mesmo argumento acima. Além disso, é provado que ao utilizar esta otimização em conjunto com a otimização do $$Find(x)$$, atingiremos a mesma complexidade $$O(\alpha(N))$$ do Union Find.
Para implementar a nova otimização do Union Find, é suficiente guardar apenas os vetores $$pai[i]$$ e $$peso[i]$$, onde $$pai[i]$$ tem o mesmo significado que no UF original e $$peso[i]$$ representa o tamanho de cada conjunto. Segue o código abaixo para melhor entendimento:
Outra aplicação interessante do Small to Large no Union Find é a possibilidade de manter uma estrutura de dados em cada conjunto, e juntá-las na função $$Join(x, y)$$ com complexidade $$O(\log N \cdot f(N))$$, onde $$f(n)$$ é a complexidade respectiva da estrutura utilizada. Se guardarmos, por exemplo, um set em cada conjunto, podemos juntá-los em $$O(\log^2 N)$$. Confira o código abaixo que demonstra essa técnica:
Rollback no Union Find
Vamos olhar o seguinte problema, dado um grafo de $$N$$ vértices podemos realizar as seguintes operações: Adicionar uma aresta, remover a última aresta adicionada e checar se existe um caminho entre dois vértices, a maneira mais fácil de resolver este problema é guardar uma lista com todas as arestas e montar o grafo das arestas atuais sempre que for checar a existência de um caminho, mas como montar o grafo e realizar a DFS é em $$O(N + M)$$ sendo $$M$$ o número de arestas no grafo atual a complexidade final seria $$O(Q \cdot (N+M))$$ sendo $$Q$$ o número de operações, essa complexidade seria muito lenta caso os limites de $$N$$ e $$Q$$ fossem maiores ou iguais a $$10^5$$.
Para resolver o problema de forma otimizada utilizaremos um Union Find, de forma que guardaremos sempre a última operação feita no Union Find em uma pilha, para isso teremos que utilizar uma versão levemente modificada do Union Find onde não utilizaremos a otimização do $$Find$$ e apenas a otimização no $$Join$$, a motivação por trás disso é que a otimização no $$Find(x)$$ modifica todos os elementos no caminho de $$x$$ até o mais acima, neste caso seria necessário guardar muitos elementos alterados, remover a otimização deixa a complexidade do Union Find em $$O(\log N)$$ como demonstrado na parte de Small-To-Large.
Toda vez que utilizarmos a operação $$Join(x, y)$$ apenas o pai do “pai da componente” de $$x$$ ou de $$y$$ será alterado, por exemplo:
Logo precisamos apenas guardar o vértice que está sendo alterado na nossa pilha de modificações.
Também precisamos notar o caso em que o $$rank$$ (altura) das componentes de $$x$$ e $$y$$ são as mesmas, nesse caso nós adicionamos $$1$$ na altura do novo pai da componente, logo precisamos guardar para cada modificação o $$x$$, o $$y$$ e um $$bool$$ afirmando se a altura foi ou não alterada.
E com isso podemos criar uma função chamada $$rollback()$$ que volta exatamente uma operação, ela pega a operação no topo da pilha e desfaz ela, alterando pai do $$y$$ de volta para $$-1$$ e diminuindo a altura do $$x$$ caso a altura tenha sido alterada, e depois removemos a operação da pilha.
Essa técnica é conhecida como Rollback no Union Find, onde a ideia é desfazer a última modificação feita, segue o código para melhor entendimento: