Disjoint Set Union ou União Busca

Este artigo discute a estrutura de dados "Disjoint Set Union" ou DSU. Também chamado de União Busca por causa de suas duas principais operações.

Essa estrutura de dados fornece os seguintes recursos. São dados vários elementos, cada um deles é um conjunto separado. Uma DSU terá uma operação para combinar dois conjuntos, e será capaz de dizer em qual conjunto um elemento específico está. A versão clássica também introduz uma terceira operação, ele pode criar um conjunto a partir de um novo elemento.

Portanto, a interface básica dessa estrutura de dados consiste em apenas três operações:

Conforme descrito em mais detalhes posteriormente, a estrutura de dados permite que você execute cada uma dessas operações em quase tempo constante $O(1)$ em média.

Também em uma das subseções, é explicada uma estrutura alternativa de um DSU, que alcança uma complexidade média mais lenta de $O(\log n)$, mas pode ser mais poderoso que a estrutura DSU comum.

Construa uma estrutura de dados eficiente

Armazenaremos os conjuntos na forma de árvores: cada árvore corresponderá a um conjunto. E a raiz da árvore será o representante / líder do conjunto.

Na imagem a seguir, a representação dessas árvores.

Example-image of the set representation with trees

No início, cada elemento começa como um único conjunto, portanto, cada vértice é sua própria árvore. Em seguida, combinamos o conjunto que contém o elemento 1 e o conjunto que contém o elemento 2. Em seguida, combinamos o conjunto que contém o elemento 3 e o conjunto que contém o elemento 4. E na última etapa, podemos mesclar os conjuntos que contêm os elementos 1 e 3.

Para a implementação, teremos que manter uma array parent que armazena uma referência ao seu ancestral imediato na árvore.

Implementação de Bruta Força

Já podemos escrever a primeira implementação da estrutura de dados Disjoint Set Union. No início, será bastante ineficiente, mas mais tarde podemos melhorá-la usando duas otimizações, para que leve um tempo quase constante para cada chamada de função.

Todas as informações sobre os conjuntos de elementos serão mantidas em um array parent.

Para criar um novo conjunto (operação make_set(v)), simplesmente criamos uma árvore com raiz no vértice v, significando que é seu próprio ancestral.

Para combinar dois conjuntos (operação union_sets(a, b)), primeiro encontramos o representante do conjunto em que a está localizado, e o representante do conjunto em que b está localizado. Se os representantes são idênticos, os conjuntos já estão mesclados. Caso contrário, podemos simplesmente especificar que um dos representantes é o pai do outro representante - combinando assim as duas árvores.

Finalmente, a implementação da função para achar o líder (operação find_set(v)): simplesmente escalamos os ancestrais do vértice v até chegarmos à raiz, i.e. um vértice tal que a referência ao ancestral seja ele mesmo. Esta operação é implementada recursivamente.

void make_set(int v) {
    parent[v] = v;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

No entanto, esta implementação é ineficiente. É fácil construir um exemplo, para que as árvores se degenerem em longas cadeias. Nesse caso, cada chamada de find_set(v) pode levar tempo $O(n)$.

Isso está longe da complexidade que queremos ter (tempo quase constante). Portanto, consideraremos duas otimizações que permitirão acelerar significativamente o trabalho.

Compressão do caminho

Essa otimização foi projetada para acelerar o find_set.

Se chamarmos find_set(v) para algum vértice v, na verdade, encontramos o representante(líder) p para todos os vértices que visitamos no caminho entre v e o líder p. O truque é tornar os caminhos para todos esses nós mais curtos, definindo o pai de cada vértice visitado diretamente como p.

Você pode ver a operação na imagem a seguir. À esquerda, há uma árvore e, no lado direito, há a árvore compactada depois de chamar find_set(7), que reduz os caminhos para os nós visitados 7, 5, 3 e 2. Achando assim um "parente absoluto".

Path compression of call <code>find_set(7)</code>

A nova implementação de find_set é a seguinte:

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

A implementação simples faz o que foi planejado: encontre primeiro o representante do conjunto (vértice raiz), e no processo os nós visitados são anexados diretamente ao representante.

Essa simples modificação da operação já atinge a complexidade do tempo $O(\log n)$ por chamada, em média. Há uma segunda modificação, que o tornará ainda mais rápido.

União por tamanho / rank

Nesta otimização, mudaremos a operação do union_set. Para ser mais preciso, mudaremos qual árvore é anexada à outra. Na implementação nativa, a segunda árvore sempre era anexada à primeira. Na prática, isso pode levar a árvores contendo cadeias de comprimento $O(n)$. Com essa otimização, evitaremos isso escolhendo com muito cuidado qual árvore será anexada.

Existem muitas heurísticas(ideias) possíveis que podem ser usadas. Mais populares são as duas abordagens a seguir: Na primeira abordagem, usamos o tamanho das árvores como classificação, e na segunda usamos a profundidade da árvore (mais precisamente, o upper_bound da profundidade da árvore, porque a profundidade será menor ao aplicar a compactação de caminho).

Em ambas as abordagens, a essência da otimização é a mesma: anexamos a árvore com a classificação mais baixa àquela com a maior.

Implementação "union-by-size":

void make_set(int v) {
    parent[v] = v;
    size[v] = 1;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (size[a] < size[b])
            swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
}

E aqui está a implementação da união por rank com base na profundidade das árvores:

void make_set(int v) {
    parent[v] = v;
    rank[v] = 0;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

Ambas as otimizações são equivalentes em termos de complexidade de tempo e espaço. Portanto, na prática, você pode usar qualquer um deles.

Complexidade do tempo

Como mencionado anteriormente, se combinarmos as duas otimizações - compactação do caminho com união por tamanho / rank - chegaremos ao tempo quase constante. Acontece que a complexidade do tempo amortizado final é $O(\alpha(n))$, onde $\alpha(n)$ é a função inversa de Ackermann, que cresce muito lentamente. De fato, cresce tão lentamente que não excede $4$ para todos razoáveis $n$ (aproximadamente $n < 10^{600}$).

Complexidade amortizada é o tempo total por operação, avaliado em uma sequência de várias operações. A idéia é garantir o tempo total de toda a sequência, enquanto permite que operações únicas sejam muito mais lentas que o tempo amortizado. E.g. no nosso caso, uma única chamada de função pode demorar $O(\log n)$ no pior dos casos, mas se fizermos $m$ chamadas consecutivas, terminaremos com um tempo médio de $O(\alpha(n))$.

Também não apresentaremos uma prova para essa complexidade de tempo, pois é bastante longa e complicada.

Além disso, vale ressaltar que o DSU com união por tamanho / rank, mas sem compressão de caminho, funciona em tempo $O(\log n)$ por query.

Vinculação por index / coin-flip linking

União por rank e união por tamanho exigem que você armazene dados adicionais para cada conjunto mantenha esses valores durante cada operação de união. Também existe um algoritmo aleatório, que simplifica um pouco a operação de união: vinculação por index.

Atribuímos a cada conjunto um valor aleatório chamado index, e anexamos o conjunto com o menor index para aquele com o maior. É provável que um conjunto maior tenha maior index do que o conjunto menor, portanto, esta operação está intimamente relacionada à união por tamanho. De fato, pode-se provar que esta operação possui a mesma complexidade de tempo que a união por tamanho. No entanto, na prática, é um pouco mais lento que a união por tamanho.

Você pode encontrar uma prova da complexidade e ainda mais técnicas de união aqui(conteúdo em inglês).

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

É um equívoco comum que apenas o lançamento de uma moeda, para decidir qual conjunto atribuímos ao outro, tenha a mesma complexidade. No entanto, isso não é verdade. O artigo vinculado acima cita que coin-flip linking combinado com compressão de caminhos tem complexidade $\Omega\left(n \frac{\log n}{\log \log n}\right)$. E nos benchmarks, o desempenho é muito pior que a união por tamanho / rank ou a vinculação por index(índice).

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

Aplicações e várias melhorias

Nesta seção, consideramos várias aplicações da estrutura de dados, além de algumas melhorias na estrutura de dados.

Componentes conectados em um grafo

Formalmente, o problema é definido da seguinte maneira: Inicialmente, temos um grafo vazio. Temos que adicionar vértices e arestas não direcionadas e responder queries como $(a, b)$ - "os vértices $a$ e $b$ estão no mesmo componente conectado do grafo?"

Aqui, podemos aplicar diretamente a estrutura de dados e obter uma solução que lida com a adição de um vértice ou uma aresta e uma query em tempo quase constante, em média.

Esta aplicação é muito importante, porque quase o mesmo problema aparece no Algoritmo de Kruskal para encontrar uma árvore geradora mínima. Usando o DSU, podemos melhorar a complexidade $ O (m \ log n + n ^ 2) $ para $ O (m \ log n) $.

Procurar componentes conectados em uma imagem

Uma das aplicações do DSU é a seguinte tarefa: existe uma imagem de $n \times m$ pixels. Originalmente, todos são brancos, mas depois alguns pixels pretos são desenhados. Você deseja determinar o tamanho de cada componente conectado branco na imagem final.

Para a solução, simplesmente iteramos sobre todos os pixels brancos da imagem, para cada célula iterar sobre seus quatro vizinhos(como um grid), e se o vizinho é branco chamar union_sets. Assim, teremos uma DSU com $n m$ nós correspondente aos pixels da imagem. As árvores resultantes no DSU são os componentes conectados desejados.

O problema também pode ser resolvido por DFS ou BFS, mas o método descrito aqui tem uma vantagem: ele pode processar a matriz linha por linha (i.e. para processar uma linha, precisamos apenas da linha anterior e da atual, e precisamos apenas de um DSU criado para os elementos de uma linha) em memória $O(\min(n, m))$.

Armazene informações adicionais para cada conjunto

O DSU permite que você armazene facilmente informações adicionais nos conjuntos.

Um exemplo simples é o tamanho dos conjuntos: o armazenamento dos tamanhos já foi descrito na seção Union by size(união por tamanho) (as informações foram armazenadas pelo atual representante/líder do conjunto).

Da mesma maneira - armazenando-o nos nós representativos - você também pode armazenar qualquer outra informação sobre os conjuntos.

Compressão de saltos ao longo de um segmento / Colorindo subarrays

Uma aplicação comum do DSU é a seguinte: Há um conjunto de vértices e cada vértice possui uma aresta de saída para outro vértice. Com o DSU, você pode encontrar o ponto final, ao qual chegamos após seguir todas as arestas de um determinado ponto inicial, em tempo quase constante.

Um bom exemplo dessa aplicação é o problema de colorir subarrays. Temos um segmento de tamanho $L$, cada elemento inicialmente tem cor 0. Temos que colorir a subarray $[l; r]$ com a cor $c$ para cada caso de teste $(l, r, c)$. No final, queremos encontrar a cor final de cada célula. Assumimos que conhecemos todas as consultas antecipadamente, ou seja, a tarefa está offline.

Para a solução, podemos criar um DSU, que para cada célula armazena um link para a próxima célula não colorida. Assim, inicialmente cada célula aponta para si mesma. Depois de colorir um segmento, todas as células daqeuele segmento irão apontar para a célula depois daquele segmento.

Agora, para resolver esse problema, consideramos as queries em ordem reversa: da última para a primeira. Dessa forma quando executarmos uma query, nós só temos que pintar exatamente as células não pintadas no subarray $[l; r]$. Todas as outras células já contêm sua cor final. Para iterar rapidamente sobre todas as células não pintadas, usamos o DSU. Encontramos a célula mais extrema esquerda que ainda não foi pintada dentro de um segmento, colorimos ela e, com o pointer, passamos para a próxima célula vazia à direita.

Aqui podemos usar o DSU com compressão de caminho, mas não podemos usar união por rank / tamanho (porque é importante quem se torna o líder após a união). Portanto, a complexidade será $O(\log n)$ por união (também é bastante rápido).

Implementação:

for (int i = 0; i <= L; i++) {
    make_set(i);
}

for (int i = m-1; i >= 0; i--) {
    int l = query[i].l;
    int r = query[i].r;
    int c = query[i].c;
    for (int v = find_set(l); v <= r; v = find_set(v)) {
        answer[v] = c;
        parent[v] = v + 1;
    }
}

Há uma otimização: Podemos usar união por rank, se armazenarmos a próxima célula não colorida em uma array adicional end[]. Então podemos mesclar dois conjuntos em um rankeado de acordo com a ideia do algoritmo, assim obtendo a solução em $O(\alpha(n))$.

Suportar distância até o vértice representativo/líder

Às vezes, em aplicações específicas do DSU, é necessário manter a distância entre um vértice e o representante de seu conjunto. (i.e. o comprimento do caminho na árvore do nó atual até a raiz da árvore).

Se não usarmos a compressão de caminho, a distância será o número de chamadas recursivas. Mas isso será ineficiente.

É possível executar uma compressão de caminhos, se nós armazenarmos a distância até o parente como um dado adicional para cada vértice.

Na implementação, é conveniente usar uma array de pares para parent[] e a função find_set agora retornar dois números: o líder do conjunto, e a distância até ele.

void make_set(int v) {
    parent[v] = make_pair(v, 0);
    rank[v] = 0;
}

pair<int, int> find_set(int v) {
    if (v != parent[v].first) {
        int len = parent[v].second;
        parent[v] = find_set(parent[v].first);
        parent[v].second += len;
    }
    return parent[v];
}

void union_sets(int a, int b) {
    a = find_set(a).first;
    b = find_set(b).first;
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = make_pair(a, 1);
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

Paridade do tamanho dos caminhos / Checar bipartividade(grafos bipartidos)

Da mesma forma que calculamos o comprimento do caminho até o líder, é possível manter a paridade do comprimento do caminho antes dele. Há várias raíze / representantes / líderes na DSU.

O requisito incomum de armazenar a paridade do caminho surge na seguinte tarefa: inicialmente nos é dado um grafo vazio, nele pode ser adicionado arestas e temos que responder queries da forma "este componente conectado contém esse vértice bipartido?".

Para resolver esse problema, criamos uma DSU para armazenar os componentes e armazenar a paridade do caminho até o representante/líder de cada vértice. Assim, podemos verificar rapidamente se a adição de uma aresta leva a uma violação da bipartividade ou não: se as extremidades da aresta estiverem no mesmo componente conectado e tiverem o mesmo comprimento de paridade para o líder, adicionar essa aresta produzirá um ciclo de comprimento ímpar, e o componente irá perder sua propriedade de bipartividade.

A dificuldade que enfrentamos é calcular a paridade no método union_find.

Se adicionarmos uma aresta $ (a, b) $ que conecte dois componentes conectados em um, então quando você anexa uma árvore a outra, precisamos ajustar a paridade.

Vamos derivar uma fórmula, que calcula a paridade emitida para o líder do conjunto que será anexado a outro conjunto. Seja $ x $ a paridade do comprimento do caminho do vértice $ a $ até o líder $ A $ e $ y $ como a paridade do comprimento do caminho do vértice $ b $ até o líder $ B $ e $ t $ a paridade desejada que devemos atribuir a $ B $ após a mesclagem. O caminho contém as três partes: de $ B $ a $ b $, de $ b $ a $ a $, que é conectado por uma borda e, portanto, tem paridade de $ 1 $ e de $ a $ a $ A $. Portanto, temos a fórmula ($ \oplus $ indica a operação XOR):

$$t = x \oplus y \oplus 1$$

Portanto, independentemente de quantas uniões realizamos, a paridade das arestas é transportada de um líder para outro.

Implementação do DSU que suporta paridade. Como na seção anterior, usamos um par para armazenar o ancestral e a paridade. Além disso, para cada conjunto, armazenamos no array bipartite [] , se ainda é bipartido ou não.

void make_set(int v) {
    parent[v] = make_pair(v, 0);
    rank[v] = 0;
    bipartite[v] = true;
}

pair<int, int> find_set(int v) {
    if (v != parent[v].first) {
        int parity = parent[v].second;
        parent[v] = find_set(parent[v].first);
        parent[v].second ^= parity;
    }
    return parent[v];
}

void add_edge(int a, int b) {
    pair<int, int> pa = find_set(a);
    a = pa.first;
    int x = pa.second;

    pair<int, int> pb = find_set(b);
    b = pb.first;
    int y = pb.second;

    if (a == b) {
        if (x == y)
            bipartite[a] = false;
    } else {
        if (rank[a] < rank[b])
            swap (a, b);
        parent[b] = make_pair(a, x^y^1);
        bipartite[a] &= bipartite[b];
        if (rank[a] == rank[b])
            ++rank[a];
    }
}

bool is_bipartite(int v) {
    return bipartite[find_set(v).first];
}

RMQ (query de range mínimo) em $O(\alpha(n))$ em média / truque de Arpa

Fornecida uma array a[] precisamos calcular alguns mínimos em segmentos da array.

A idéia para resolver esse problema com o DSU é a seguinte: Iremos iterar sobre a array e quando estivermos no iésimo elemento iremos responder todas as queries (L, R) com R == i. Para fazer isso com eficiência, manteremos um DSU usando os primeiros i elementos com a seguinte estrutura: o pai de um elemento é o próximo elemento menor à direita dele. Usando essa estrutura a resposta dessa query será a[find_set(L)], o menor número à direita de L.

Essa ideia apenas funciona offline, i.e. se soubermos dos casos de teste(queries) antecipadamente.

Podemos aplicar compressão de caminhos. Também podemos usar união por rank, se armazenarmos o líder atual em uma array separada.

struct Query {
    int L, R, idx;
};

vector<int> answer;
vector<vector<Query>> container;

container[i] contém todos os casos(queries) com R == i.

stack<int> s;
for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] > a[i]) {
        parent[s.top()] = i;
        s.pop();
    }
    s.push(i);
    for (Query q : container[i]) {
        answer[q.idx] = a[find_set(q.L)];
    }
}

Atualmente, esse algoritmo é conhecido como truque de Arpa. É nomeado após AmirReza Poorakhavan, que descobriu e popularizou independentemente essa técnica. Embora esse algoritmo já existisse.

LCA (Menor Ancestral Comum em uma Árvore) em $O(\alpha(n))$ em média

O algoritmo para encontrar o LCA é discutido em Menor Ancestral Comum - algoritmo de Tarjan. Este algoritmo compara-se favorável com outros algoritmos para encontrar o LCA devido à sua simplicidade (especialmente comparado à um algoritmo otimizado como Farach-Colton and Bender).

Armazenando o DSU explicitamente em uma lista de conjuntos / Aplicações dessa ideia juntando várias estruturas de dados

Uma das formas alternativas de armazenar o DSU é a preservação de cada conjunto na forma de um lista explícita de armazenamento de seus elementos. Cada elemento da lista armazena uma referência ao seu representativo/líder.

À primeira vista, isso parece uma estrutura de dados ineficiente: combinando dois conjuntos, teremos que adicionar uma lista ao final de outra e precisar atualizar a liderança em todos os elementos de uma das listas.

No entanto, o uso de uma outra ideia (similar com a união por tamanho) pode reduzir significativamente a complexidade : $O(m + n \log n)$ para executar $m$ queries nos $n$ elementos.

A ideia é que sempre iremos adicione o menor dos dois conjuntos ao conjunto maior. A adição de um conjunto a outro pode ser implementada na função union_sets e levará um tempo proporcional ao tamanho do conjunto adicionado. And the search for the leader in find_set will take $O(1)$ with this method of storing.

Vamos provar a complexidade do tempo $O(m + n \log n)$ para a execução de $m$ queries. Vamos assumir um elemento arbitrário $x$ e contar quantas vezes ele foi afetado na operação de mesclagem(junção) union_sets. Quando o elemento $x$ é afetado pela primeira vez, o tamanho do novo conjunto será pelo menos $2$. Quando é afetado pela segunda vez, o conjunto resultante terá um tamanho de pelo menos $4$, porque o conjunto menor é adicionado ao maior. E assim por diante. Isso significa, que $x$ só pode ser movido no máximo $\log n$ operações de junção(união). Assim, a soma de todos os vértices dá $O(n \log n)$ + $O(1)$ para cada chamada.

Implementação:

vector<int> listt[MAXN];
int parent[MAXN];

void make_set(int v) {
    listt[v] = vector<int>(1, v);
    parent[v] = v;
}

int find_set(int v) {
    return parent[v];
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (listt[a].size() < listt[b].size())
            swap(a, b);
        while (!listt[b].empty()) {
            int v = listt[b].back();
            listt[b].pop_back();
            parent[v] = a;
            listt[a].push_back (v);
        }
    }
}

Essa ideia de adicionar a parte menor a uma parte maior também pode ser usada em muitas soluções que nada têm a ver com DSU.

Por exemplo, considere o problema: nos é dada uma árvore, cada folha tem um número atribuído (um mesmo número pode aparecer várias vezes em folhas diferentes). Queremos calcular o número de diferentes números na subárvore para cada nó da árvore.

Aplicando a mesma ideia para esse problema: podemos implementar uma DFS, que retornará um pointer para um conjunto de números inteiros - uma lista de números naquela subárvore. Portanto, para conseguir a resposta para o nó atual (a não ser que seja uma folha), chamamos a DFS para cada criança daquele nó, e juntamos(união) os conjuntos recebidos. O tamanho do conjunto resultante será a resposta para o nó atual. Para combinar com eficiência vários conjuntos, apenas aplicamos a receita acima descrita: juntamos os conjuntos simplesmente adicionando os menores aos maiores. No final temos uma solução $O(n \log^2 n)$, porque um número será adicionado apenas a um conjunto no máximo $O(\log n)$ vezes.

Armazenando o DSU e mantendo uma estrutura em árvore / Econtrando pontes online em $O(\alpha(n))$ (média)

Uma das aplicações mais poderosas do DSU é que ele permite armazenar ambas árvores comprimidas(compressas) e não comprimidas. A forma compressa pode ser usada para unir árvores e para verificar se dois vértices estão na mesma árvore, e a forma não compressa pode ser aplicada - por exemplo - para procurar caminhos entre dois vértices, ou outras travessias da estrutura da árvore.

Na implementação, isso significa que, além da array ancestral compressa parent[] precisaremos manter a array de ancestrais não compressos real_parent[]. É importante que mantendo essa array adicional não irá piorar a complexidade: mudanças só ocorrem quando unimos duas árvores, e apenas em um elemento.

Por outro lado, quando aplicados na prática, geralmente precisamos conectar árvores usando uma aresta especificada diferente daquela usando os dois nós raiz. Isso significa que não temos outra escolha senão mudar a raiz uma das árvores (fazer das extremidades da aresta a nova raiz da árvore).

À primeira vista, parece que esse novo enraizamento é muito caro e piora bastante a complexidade do tempo. De fato, para enraizar uma árvore no vértice $v$ devemos ir do vértice para a raiz antiga e mudar de direção parent[] e real_parent[] para todos os nós nesse caminho.

No entanto, na realidade, não é tão ruim, podemos simplesmente mudar a raiz da menor das duas árvores, semelhante às idéias nas seções anteriores, e obter $O(\log n)$ em média.

Mais detalhes (incluindo a prova da complexidade do tempo) podem ser encontrados em "Encontrando Pontes".

Retrospectiva Histórica

A estrutura de dados DSU é conhecida há muito tempo.

Essa maneira de armazenar essa estrutura no formato de uma floresta de árvores aparentemente, foi descrito pela primeira vez por Galler e Fisher em 1964 (Galler, Fisher, "Um algoritmo de equivalência aprimorado), no entanto, a análise completa da complexidade do tempo foi conduzida muito mais tarde.

As otimizações "compressão de caminhos" e "União por rank" foram desenvolvidas por McIlroy e Morris, e independente deles, também por Tritter.

Hopcroft e Ullman mostraram em 1973 a complexidade do tempo $O(\log^\star n)$ (Hopcroft, Ullman "Set-merging algorithms") - aqui $\log^\star$ é o logaritmo iterado (essa é uma função de crescimento lento, mas ainda não tão lenta quanto a função inversa de Ackermann).

Pela primeira vez a avaliação de $O(\alpha(n))$ foi mostrada em 1975 (Tarjan "Efficiency of a Good But Not Linear Set Union Algorithm"). Mais tarde em 1985 ele, junto com Leeuwen, publicaram várias análises de complexidade e ideias de comprimir o caminho (Tarjan, Leeuwen "Worst-case Analysis of Set Union Algorithms").

Finalmente em 1989 Fredman e Sachs provou que no modelo de computação adotado qualquer algoritmo para o problema do disjoint set union tem que trabalhar em tempo, pelo menos $O(\alpha(n))$ (Fredman, Saks, "The cell probe complexity of dynamic data structures").

No entanto, deve-se notar também que existem vários artigos disputando avaliação provisória e afirmando que o DSU com compressão de caminhos e União por rank é executado em $O(1)$ em média (Zhang "The Union-Find Problem Is Linear", Wu, Otoo "A Simpler Proof of the Average Case Complexity of Union-Find with Path Compression").

Problemas