Conjuntos Disjuntos

Uma estrutura de união de conjuntos disjuntos mantém uma partição dos elementos em conjuntos sem sobreposição.

• makeSet(x) cria um conjunto unitário.
• find(x) retorna um representante do conjunto de x.
• union(a, b) une dois conjuntos quando são distintos.

Representação por floresta

Cada elemento aponta para um pai; uma raiz representa seu conjunto. Duas otimizações complementares tornam as operações extremamente eficientes:

• união por rank ou tamanho: anexa a árvore menor ou menos profunda sob a outra;
• compressão de caminho: redireciona os nós visitados para a raiz durante find.

final class DisjointSet {
    private final int[] parent;
    private final int[] size;

    DisjointSet(int n) {
        if (n < 0) throw new IllegalArgumentException("negative size");
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;
        if (size[rootA] < size[rootB]) {
            int temporary = rootA;
            rootA = rootB;
            rootB = temporary;
        }
        parent[rootB] = rootA;
        size[rootA] += size[rootB];
        return true;
    }
}

Ao longo de uma sequência de operações, o tempo amortizado é O(α(n)), em que a função inversa de Ackermann cresce tão lentamente que seu valor é muito pequeno para tamanhos práticos de entrada. Isso não é literalmente constante no sentido matemático.

Aplicações

Use conjuntos disjuntos para conectividade incremental não direcionada, o algoritmo de árvore geradora mínima de Kruskal e o agrupamento de classes de equivalência. Eles não aceitam diretamente a remoção de arestas nem a reconstrução de caminhos.