Union-Find (Disjoint Set Union - DSU)

1. O Canivete Suíço da Conectividade

O problema de Conectividade Dinâmica pergunta: 1. Os elementos \(A\) e \(B\) estão conectados? 2. Por favor, conecte \(A\) e \(B\) agora.

Diferente de BFS/DFS que analisam um grafo estático, o Union-Find é perfeito para quando as arestas são adicionadas dinamicamente. - É a estrutura por trás do Kruskal. - É usado para detectar ciclos em tempo real. - É usado em processamento de imagens (rotulação de componentes).

2. A Estrutura Básica (Floresta)

Imagine cada elemento como um nó. Cada conjunto é uma árvore. A Raiz da árvore é o “Líder” (Representante) do conjunto. - Se Find(A) == Find(B), então eles têm o mesmo líder, logo estão conectados. - Para fazer Union(A, B), fazemos a raiz de A apontar para a raiz de B (ou vive-versa).

Arrays Necessários

  • parent[i]: Armazena o pai do nó i. Se parent[i] == i, ele é a raiz.

3. As Duas Otimizações Críticas

Sem otimizações, a árvore pode virar uma linha reta (Linked List), e o Find fica \(O(N)\). Com elas, fica praticamente \(O(1)\).

3.1. Path Compression (Achatamento de Caminho)

Ao subir de um nó até a raiz durante o Find, aproveitamos para reconectar todos os nós visitados diretamente à raiz. Isso achata a árvore brutalmente.

public int find(int i) {
    if (parent[i] == i) 
        return i;
    
    // Mágica Recursiva: Atualiza o pai para ser a raiz suprema
    return parent[i] = find(parent[i]); 
}

3.2. Union by Rank/Size (União Inteligente)

Ao unir duas árvores, sempre pendure a menor (menos profunda ou com menos nós) na maior. Isso evita que a árvore cresça desnecessariamente em altura.

// Variáveis globais
int[] parent;
int[] size; // ou 'rank'

public void union(int i, int j) {
    int rootI = find(i);
    int rootJ = find(j);
    
    if (rootI != rootJ) {
        // Otimização: A menor entra na maior
        if (size[rootI] < size[rootJ]) {
            int temp = rootI; rootI = rootJ; rootJ = temp;
        }
        
        parent[rootJ] = rootI; // rootJ agora é filho de rootI
        size[rootI] += size[rootJ];
    }
}

4. Implementação Completa e Segura

public class DSU {
    private int[] parent;
    private int[] size;
    private int numSets; // Útil para saber quantos componentes restam

    public DSU(int n) {
        parent = new int[n];
        size = new int[n];
        numSets = n;
        
        for (int i = 0; i < n; i++) {
            parent[i] = i; // Cada um é seu próprio pai
            size[i] = 1;
        }
    }

    public int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]); // Path Compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);

        if (rootI != rootJ) {
            // Union by Size
            if (size[rootI] < size[rootJ]) {
                // i é menor, j manda
                parent[rootI] = rootJ;
                size[rootJ] += size[rootI];
            } else {
                // j é menor, i manda
                parent[rootJ] = rootI;
                size[rootI] += size[rootJ];
            }
            numSets--; // Dois conjuntos viraram um
        }
    }
    
    public boolean isSameSet(int i, int j) {
        return find(i) == find(j);
    }
    
    public int getSize(int i) {
        return size[find(i)];
    }
}

5. Análise de Complexidade: A Função de Ackermann

Com as duas otimizações (Path Compression + Union by Rank), a complexidade amortizada de cada operação é \(O(\alpha(N))\). \(\alpha(N)\) é a inversa da função de Ackermann. Para ter uma ideia: - \(Ackermann(4, 4)\) é um número maior que o número de átomos no universo observável. - Logo, \(\alpha(N) \le 4\) para qualquer dado que caiba num computador.

Na prática, consideramos \(O(1)\) (tempo constante). É uma das estruturas mais eficientes da Ciência da Computação.

Back to top