Informática - Ideia 05

Escrito por Lúcio Figueiredo e Thiago Mota

Conhecimento prévio necessário:

1. Union Find

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: