# Aula 03 - Union Find

### Referências úteis

* https://algs4.cs.princeton.edu/15uf/ - capítulo do algs4 sobre union find

***



## Conjuntos disjuntos



* Seja S = {$S_1, S_2, ..., S_n$} uma coleção de conjuntos disjuntos ou seja $S_i \cap S_j = \empty $ , para todo i e j
* Coleção disjunta dinâmica : Conjuntos são modificados ao longo do tempo
  * Ex : grafo dinâmico.
    * Inicialmente, cada item do grafo está disjunto, é um conjunto disjunto
    * Posteriormente, posso montar arestas entre os itens e conectá-los, e monto um componente (chamamos assim no caso de grafo)/conjunto.
* Quero montar uma API com operações que acrescenta arestas, encontra ligações...

``` java
public Class (QuickFind/QuickUnionr)UF { //quick find e quick union são implementações diferentes pra essa classe
    private int[] pai;
    private int[] sz;
    private int count;
    public _ UF (int n) {
        count = n;
        pai = new int[n];
        sz = new int[n];
        for (int i = 0; i < n; i++) {
            id[i]  = i;
            sz[i] = 1;
            
        }
    }
    
    public int count() {
        return count;
    }
    
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
    
    public int find(int p) {
        while(p != pai[p]) 
            	pai[p] = pai[pai[p]];
            	p = pai;
            
        }
       return p;
    }
    
    public void union (int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID)
            	return;
        if (sz[pID] < sz[qID]) {
            pai[pID] = qID;
            sz[qID] += sz[pId];
        }
        else {
            pai[qID] = pID;
            sz[pID] += sz[qID]; 
        }
        pai[pID] = qID;
        count--;
    }
}
```

***

### Invariante

* Toda árvore de altura h tem pelo menos $2^h$ elementos portanto, $lg(n) >= h$. 

### Análise de tempo

​	1a linha : implementação com o vetor de IDs (qual o ID do conjunto que o elemento está)

​	2a linha : agora os caras são organizados pelo pai, o que faz demorar mais o find e o union fica mais demorado porque depende de find - implementação usando florestas disjuntas

​	3a linha: vamos juntar o menor grupo ao maior : **union by size**. Dessa forma eu minimizo o custo do find nas operções de find.

​	

| UF(n)  | union       | find       |
| ------ | ----------- | ---------- |
| $O(n)$ | $O(n)$      | $O(1)$     |
| $O(n)$ | $O(n)$      | $O(n)$     |
| $O(n)$ | $O(lg(n)) $ | $O(lg(n))$ |

## Pior caso do weighted quick union

- Quando usamos o QuickUnion normal, a altura do grafo pode aumentar a cada operação de union
- Mas usando o weighted quickUnion, a altura só aumenta quando voce dobra o número de caras

------



## Path Compression UF

- Ideia : encurtar os caminhos durante cada find()
  - A cada vez que eu rodo o find e procuro quem é o pai de uma arvore, eu aproveito e pego todos os filhos e ligo diretamente ao pai

```java
public int find (int p) {
    if (p != pai[p])
        pai[p] = find(pai[p]);
    return pai[p];  
    }
}
```

### Consumo de tempo amortizado (union c/ path compression find) : 

$$
O(lg^*n)
$$

- Uma função log-estrela é definida como : 

  - Uma função lg-estrela é o menor k tal que 
    $$
    lg(lg(lg(...(n)))) <= 1
    $$

  - Ex : 
    $$
    lg(8) = 3, lg(3) \approx 1 \therefore lg^*8 = 2
    $$