A estrutura de dados Union-Find, também conhecida como Disjoint Set Union (DSU), é uma ferramenta algorítmica essencial para gerenciar uma partição de um conjunto de elementos em diversos subconjuntos disjuntos. Ela é amplamente utilizada em cenários onde precisamos agrupar elementos e verificar rapidamante se dois itens pertencem ao mesmo grupo.

1. Fundamentos do Union-Find

O conceito central do Union-Find baseia-se em dois processos principais: agrupar n elementos distintos em conjuntos que não se sobrepõem e consultar a qual conjunto um determinado elemento pertence. Inicialmente, cada elemento é tratado como um conjunto individual (um "nó" que é sua própria raiz).

Para ilustrar, imagine um cenário com 10 indivíduos numerados de 0 a 9. Inicialmente, todos são desconhecidos entre si:

Índices: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Valores: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

Se dividirmos esses indivíduos em três grupos baseados em sua localização — por exemplo, Grupo A {0, 6, 7, 8}, Grupo B {1, 4, 9} e Grupo C {2, 3, 5} — definimos um "líder" ou "raiz" para cada grupo (digamos, 0, 1 e 2). O estado interno da estrutura mudaria para refletir que os outros membros apontam para o seu respectivo líder.

Conclusões sobre a representação em array:

• O índice do array representa a identidade do elemento.
• Valores negativos indicam que o elemento é a raiz de um conjunto. O valor absoluto pode representar o tamanho do conjunto.
• Valores não negativos indicam o índice do "pai" daquele elemento, permitindo navegar até a raiz.

Quando dois grupos decidem se fundir, a raiz de um grupo passa a apontar para a raiz do outro, unificando todos os membros sob um único líder supremo.

2. Implementação em C++

Abaixo, apresentamos uma implementação robusta utilizando templates, focando na clareza do fluxo de união e busca.

#include <vector>
#include <cstddef>

template <typename T>
class DSU {
public:
    DSU(size_t n) : _parent_map(n, -1) {}

    // Encontra a raiz do conjunto ao qual o elemento 'i' pertence
    int find(int i) {
        int root = i;
        while (_parent_map[root] >= 0) {
            root = _parent_map[root];
        }
        return root;
    }

    // Une os conjuntos contendo os elementos 'i' e 'j'
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);

        if (root_i != root_j) {
            // Consolida o tamanho no novo líder
            _parent_map[root_i] += _parent_map[root_j];
            // O líder de j agora aponta para o líder de i
            _parent_map[root_j] = root_i;
        }
    }

    // Verifica se dois elementos pertencem ao mesmo conjunto
    bool is_connected(int i, int j) {
        return find(i) == find(j);
    }

    // Retorna a quantidade total de conjuntos disjuntos
    size_t count_sets() const {
        size_t count = 0;
        for (const auto& val : _parent_map) {
            if (val < 0) count++;
        }
        return count;
    }

private:
    std::vector<int> _parent_map;
};

3. Aplicações Práticas

O Union-Find é a base para resolver problemas de conectividade em grafos e consistência lógica. Abaixo, dois exemplos clássicos adaptados para demonstrar sua versatilidade.

Exemplo A: Contagem de Províncias (Componentes Conectados)

Neste problema, recebemos uma matriz de adjacência indicando conexões entre cidades. O objetivo é contar quantos grupos independentes de cidades (províncias) existem.

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int> nodes(n, -1);

        auto get_root = [&nodes](int x) {
            while (nodes[x] >= 0) x = nodes[x];
            return x;
        };

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (isConnected[i][j]) {
                    int r1 = get_root(i);
                    int r2 = get_root(j);
                    if (r1 != r2) {
                        nodes[r1] += nodes[r2];
                        nodes[r2] = r1;
                    }
                }
            }
        }

        int provinces = 0;
        for (int val : nodes) {
            if (val < 0) provinces++;
        }
        return provinces;
    }
};

Exemplo B: Verificação de Equações de Igualdade

Dado um conjunto de strings como "a==b" ou "c!=d", precisamos determinar se todas as restrições podem ser satisfeitas simultaneamnete sem contradições.

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        vector<int> alphabet(26, -1);

        auto find_leader = [&alphabet](int x) {
            while (alphabet[x] >= 0) x = alphabet[x];
            return x;
        };

        // Passo 1: Processar todas as igualdades para formar os grupos
        for (const string& eq : equations) {
            if (eq[1] == '=') {
                int leader1 = find_leader(eq[0] - 'a');
                int leader2 = find_leader(eq[3] - 'a');
                if (leader1 != leader2) {
                    alphabet[leader1] += alphabet[leader2];
                    alphabet[leader2] = leader1;
                }
            }
        }

        // Passo 2: Validar se as desigualdades não conflitam com os grupos formados
        for (const string& eq : equations) {
            if (eq[1] == '!') {
                int leader1 = find_leader(eq[0] - 'a');
                int leader2 = find_leader(eq[3] - 'a');
                if (leader1 == leader2) return false;
            }
        }

        return true;
    }
};