Union-Find / conjuntos disjuntos (DSU)

Este artículo trata la estructura de datos conjuntos disjuntos (Disjoint Set Union o DSU). A menudo también se la llama Union-Find por sus dos operaciones principales.

Esta estructura de datos ofrece las siguientes capacidades. Se nos dan varios elementos, cada uno de los cuales es un conjunto separado. Un DSU tendrá una operación para combinar dos conjuntos cualesquiera, y podrá indicar en qué conjunto se encuentra un elemento específico. La versión clásica también introduce una tercera operación: puede crear un conjunto a partir de un elemento nuevo.

Así, la interfaz básica de esta estructura de datos consiste en solo tres operaciones:

make_set(v) - crea un conjunto nuevo formado por el elemento nuevo v
union_sets(a, b) - fusiona los dos conjuntos indicados (el conjunto en el que está el elemento a y el conjunto en el que está el elemento b)
find_set(v) - devuelve el representante (también llamado líder) del conjunto que contiene el elemento v. Este representante es un elemento de su conjunto correspondiente. Lo elige la propia estructura de datos en cada conjunto (y puede cambiar con el tiempo, concretamente después de llamadas a union_sets). Este representante se puede usar para comprobar si dos elementos pertenecen al mismo conjunto o no. a y b están exactamente en el mismo conjunto si find_set(a) == find_set(b). En caso contrario están en conjuntos distintos.

Como se describe con más detalle más adelante, la estructura de datos permite realizar cada una de estas operaciones en tiempo casi $O(1)$ en promedio.

Además, en una de las subsecciones se explica una estructura alternativa de DSU, que alcanza una complejidad promedio más lenta de $O(\log n)$ , pero que puede ser más potente que la estructura DSU habitual.

Construir una estructura de datos eficiente

Almacenaremos los conjuntos en forma de árboles: cada árbol corresponderá a un conjunto. Y la raíz del árbol será el representante/líder del conjunto.

En la siguiente imagen se puede ver la representación de esos árboles.

Imagen de ejemplo de la representación de conjuntos con árboles

Al principio, cada elemento empieza como un conjunto de un solo elemento, por lo tanto cada vértice es su propio árbol. Luego combinamos el conjunto que contiene el elemento 1 y el conjunto que contiene el elemento 2. Después combinamos el conjunto que contiene el elemento 3 y el conjunto que contiene el elemento 4. Y en el último paso, combinamos el conjunto que contiene el elemento 1 y el conjunto que contiene el elemento 3.

Para la implementación esto significa que tendremos que mantener un arreglo parent que guarda una referencia a su ancestro inmediato en el árbol.

Implementación ingenua

Ya podemos escribir la primera implementación de la estructura de datos Union-Find / conjuntos disjuntos. Al principio será bastante ineficiente, pero más adelante la mejoraremos con dos optimizaciones, de modo que cada llamada a función tome tiempo casi constante.

Como dijimos, toda la información sobre los conjuntos de elementos se guardará en un arreglo parent.

Para crear un conjunto nuevo (operación make_set(v)), simplemente creamos un árbol con raíz en el vértice v, lo que significa que es su propio ancestro.

Para combinar dos conjuntos (operación union_sets(a, b)), primero encontramos el representante del conjunto en el que está a y el representante del conjunto en el que está b. Si los representantes son idénticos, no hay nada que hacer: los conjuntos ya están fusionados. En caso contrario, podemos simplemente indicar que uno de los representantes es el padre del otro representante, y con ello combinamos los dos árboles.

Por último, la implementación de la función que busca el representante (operación find_set(v)): simplemente subimos por los ancestros del vértice v hasta llegar a la raíz, es decir, a un vértice tal que la referencia al ancestro apunta a sí mismo. Esta operación se implementa fácilmente de forma recursiva.


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;
}

Sin embargo esta implementación es ineficiente. Es fácil construir un ejemplo en el que los árboles degeneran en cadenas largas. En ese caso cada llamada find_set(v) puede tomar $O(n)$ de tiempo.

Esto está muy lejos de la complejidad que queremos tener (tiempo casi constante). Por lo tanto consideraremos dos optimizaciones que permitirán acelerar el trabajo de forma significativa.

Optimización de compresión de caminos

Esta optimización está pensada para acelerar find_set.

Si llamamos a find_set(v) para algún vértice v, en realidad encontramos el representante p para todos los vértices que visitamos en el camino entre v y el representante real p. El truco consiste en acortar los caminos de todos esos nodos, asignando como padre de cada vértice visitado directamente a p.

Se puede ver la operación en la siguiente imagen. A la izquierda hay un árbol, y a la derecha está el árbol comprimido después de llamar a find_set(7), que acorta los caminos de los nodos visitados 7, 5, 3 y 2.

Compresión de caminos de la llamada find_set(7)

La nueva implementación de find_set es la siguiente:


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

La implementación simple hace lo que se pretendía: primero encuentra el representante del conjunto (vértice raíz), y luego, en el proceso de desenrollado de la pila, los nodos visitados se cuelgan directamente del representante.

Esta modificación simple de la operación ya alcanza la complejidad temporal $O(\log n)$ por llamada en promedio (aquí sin demostración). Hay una segunda modificación que lo hará todavía más rápido.

Unión por tamaño / rango

En esta optimización cambiaremos la operación union_set. Para ser precisos, cambiaremos qué árbol se cuelga del otro. En la implementación ingenua el segundo árbol siempre se colgaba del primero. En la práctica eso puede producir árboles que contienen cadenas de longitud $O(n)$ . Con esta optimización evitaremos esto eligiendo con mucho cuidado qué árbol se cuelga.

Hay muchas heurísticas posibles que se pueden usar. Las más populares son los dos enfoques siguientes: En el primero usamos el tamaño de los árboles como rango, y en el segundo usamos la profundidad del árbol (más precisamente, una cota superior de la profundidad del árbol, porque la profundidad se reduce al aplicar la compresión de caminos).

En ambos enfoques la esencia de la optimización es la misma: colgamos el árbol de menor rango del árbol de mayor rango.

Aquí está la implementación de la unión por tamaño:


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];
    }
}

Y aquí está la implementación de la unión por rango basada en la profundidad de los árboles:


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 optimizaciones son equivalentes en términos de complejidad temporal y espacial. Así que en la práctica se puede usar cualquiera de ellas.

Complejidad temporal

Como se mencionó antes, si combinamos ambas optimizaciones —compresión de caminos con unión por tamaño / rango— alcanzaremos consultas en tiempo casi constante. Resulta que la complejidad temporal amortizada final es $O(\alpha(n))$ , donde $\alpha(n)$ es la función inversa de Ackermann, que crece muy lentamente. De hecho crece tan lento que no supera $4$ para todo $n$ razonable (aproximadamente $n < 10^{600}$ ).

La complejidad amortizada es el tiempo total por operación, evaluado sobre una secuencia de varias operaciones. La idea es garantizar el tiempo total de toda la secuencia, permitiendo que operaciones individuales sean mucho más lentas que el tiempo amortizado. P. ej. en nuestro caso una sola llamada podría tomar $O(\log n)$ en el peor caso, pero si hacemos $m$ de esas llamadas seguidas terminaremos con un tiempo promedio de $O(\alpha(n))$ .

Tampoco presentaremos una demostración de esta complejidad temporal, ya que es bastante larga y complicada.

Además, vale la pena mencionar que el DSU con unión por tamaño / rango, pero sin compresión de caminos, funciona en $O(\log n)$ de tiempo por consulta.

Enlace por índice / enlace por lanzamiento de moneda

Tanto la unión por rango como la unión por tamaño requieren guardar datos adicionales para cada conjunto, y mantener esos valores durante cada operación de unión. También existe un algoritmo aleatorizado que simplifica un poco la operación de unión: el enlace por índice.

Asignamos a cada conjunto un valor aleatorio llamado índice, y colgamos el conjunto de menor índice del de mayor índice. Es probable que un conjunto más grande tenga un índice mayor que el conjunto más pequeño, por lo tanto esta operación está estrechamente relacionada con la unión por tamaño. De hecho se puede demostrar que esta operación tiene la misma complejidad temporal que la unión por tamaño. Sin embargo en la práctica es un poco más lenta que la unión por tamaño.

Se puede encontrar una demostración de la complejidad y todavía más técnicas de unión aquí .


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;
    }
}

Es un error común pensar que simplemente lanzar una moneda para decidir qué conjunto colgamos del otro tiene la misma complejidad. Sin embargo eso no es cierto. El artículo enlazado arriba conjetura que el enlace por lanzamiento de moneda combinado con la compresión de caminos tiene complejidad $\Omega\left(n \frac{\log n}{\log \log n}\right)$ . Y en benchmarks se desempeña mucho peor que la unión por tamaño/rango o el enlace por í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;
    }
}

Aplicaciones y varias mejoras

En esta sección consideramos varias aplicaciones de la estructura de datos, tanto los usos triviales como algunas mejoras de la estructura.

Componentes conexas en un grafo

Esta es una de las aplicaciones evidentes del DSU.

Formalmente el problema se define de la siguiente manera: Inicialmente tenemos un grafo vacío. Hay que agregar vértices y aristas no dirigidas, y responder consultas de la forma $(a, b)$ — «¿los vértices $a$ y $b$ están en la misma componente conexa del grafo?».

Aquí podemos aplicar la estructura de datos de forma directa, y obtener una solución que maneja la adición de un vértice o una arista y una consulta en tiempo casi constante en promedio.

Esta aplicación es bastante importante, porque casi el mismo problema aparece en el algoritmo de Kruskal para encontrar un árbol de expansión mínima. Usando DSU podemos mejorar la complejidad $O(m \log n + n^2)$ a $O(m \log n)$ .

Búsqueda de componentes conexas en una imagen

Una de las aplicaciones del DSU es la siguiente tarea: hay una imagen de $n \times m$ píxeles. Originalmente todos son blancos, pero luego se dibujan algunos píxeles negros. Queremos determinar el tamaño de cada componente conexa blanca en la imagen final.

Para la solución simplemente iteramos sobre todos los píxeles blancos de la imagen, para cada celda iteramos sobre sus cuatro vecinos, y si el vecino es blanco llamamos a union_sets. Así tendremos un DSU con $n m$ nodos correspondientes a los píxeles de la imagen. Los árboles resultantes en el DSU son las componentes conexas deseadas.

El problema también se puede resolver con DFS o BFS, pero el método descrito aquí tiene una ventaja: puede procesar la matriz fila por fila (es decir, para procesar una fila solo necesitamos la fila anterior y la actual, y solo necesitamos un DSU construido para los elementos de una fila) en $O(\min(n, m))$ de memoria.

Guardar información adicional para cada conjunto

El DSU permite guardar fácilmente información adicional en los conjuntos.

Un ejemplo simple es el tamaño de los conjuntos: guardar los tamaños ya se describió en la sección Unión por tamaño (la información se guardaba en el representante actual del conjunto).

De la misma manera —guardándola en los nodos representantes— también se puede guardar cualquier otra información sobre los conjuntos.

Comprimir saltos a lo largo de un segmento / Pintar subarreglos offline

Una aplicación común del DSU es la siguiente: Hay un conjunto de vértices, y cada vértice tiene una arista saliente hacia otro vértice. Con DSU se puede encontrar el punto final al que se llega después de seguir todas las aristas desde un punto de partida dado, en tiempo casi constante.

Un buen ejemplo de esta aplicación es el problema de pintar subarreglos. Tenemos un segmento de longitud $L$ , cada elemento inicialmente tiene el color 0. Hay que repintar el subarreglo $[l, r]$ con el color $c$ para cada consulta $(l, r, c)$ . Al final queremos encontrar el color final de cada celda. Suponemos que conocemos todas las consultas de antemano, es decir, la tarea es offline.

Para la solución podemos hacer un DSU que, para cada celda, guarda un enlace a la siguiente celda sin pintar. Así, inicialmente cada celda apunta a sí misma. Después de ejecutar un repintado pedido de un segmento, todas las celdas de ese segmento apuntarán a la celda que está después del segmento.

Ahora, para resolver este problema, consideramos las consultas en orden inverso: de la última a la primera. De este modo, cuando ejecutamos una consulta, solo tenemos que pintar exactamente las celdas sin pintar del subarreglo $[l, r]$ . Todas las demás celdas ya contienen su color final. Para iterar rápidamente sobre todas las celdas sin pintar, usamos el DSU. Encontramos la celda sin pintar más a la izquierda dentro de un segmento, la repintamos, y con el puntero nos movemos a la siguiente celda vacía a la derecha.

Aquí podemos usar el DSU con compresión de caminos, pero no podemos usar unión por rango / tamaño (porque importa quién queda como líder después de la fusión). Por lo tanto la complejidad será $O(\log n)$ por unión (que también es bastante rápido).

Implementación:


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;
    }
}

Hay una optimización: podemos usar unión por rango / tamaño si guardamos la siguiente celda sin pintar en un arreglo adicional end[]. Entonces podemos fusionar dos conjuntos en uno según sus heurísticas, y obtenemos la solución en $O(\alpha(n))$ .

Mantener distancias hasta el representante

A veces, en aplicaciones específicas del DSU, hay que mantener la distancia entre un vértice y el representante de su conjunto (es decir, la longitud del camino en el árbol desde el nodo actual hasta la raíz del árbol).

Si no usamos compresión de caminos, la distancia es simplemente el número de llamadas recursivas. Pero esto será ineficiente.

Sin embargo es posible hacer compresión de caminos si guardamos la distancia al padre como información adicional para cada nodo.

En la implementación es conveniente usar un arreglo de pares para parent[] y la función find_set ahora devuelve dos números: el representante del conjunto y la distancia hasta él.


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]++;
    }
}

Mantener la paridad de la longitud del camino / Verificar bipartitud online

De la misma manera que al calcular la longitud del camino hasta el líder, es posible mantener la paridad de la longitud del camino hasta él. ¿Por qué esta aplicación está en un párrafo separado?

El requisito inusual de guardar la paridad del camino aparece en la siguiente tarea: inicialmente se nos da un grafo vacío, se le pueden agregar aristas, y hay que responder consultas de la forma «¿la componente conexa que contiene este vértice es bipartita?».

Para resolver este problema, hacemos un DSU para guardar las componentes y guardamos la paridad del camino hasta el representante para cada vértice. Así podemos comprobar rápidamente si agregar una arista viola la bipartitud o no: concretamente, si los extremos de la arista están en la misma componente conexa y tienen la misma paridad de longitud hasta el líder, entonces agregar esta arista producirá un ciclo de longitud impar, y la componente perderá la propiedad de ser bipartita.

La única dificultad que enfrentamos es calcular la paridad en el método union_find.

Si agregamos una arista $(a, b)$ que conecta dos componentes conexas en una, entonces al colgar un árbol de otro hay que ajustar la paridad.

Derivemos una fórmula que calcula la paridad asignada al líder del conjunto que se colgará de otro conjunto. Sea $x$ la paridad de la longitud del camino desde el vértice $a$ hasta su líder $A$ , e $y$ la paridad de la longitud del camino desde el vértice $b$ hasta su líder $B$ , y $t$ la paridad deseada que hay que asignar a $B$ después de la fusión. El camino consiste en tres partes: de $B$ a $b$ , de $b$ a $a$ , que está conectado por una arista y por lo tanto tiene paridad $1$ , y de $a$ a $A$ . Por lo tanto obtenemos la fórmula ( $\oplus$ denota la operación XOR):

$t = x \oplus y \oplus 1$

Así, independientemente de cuántas uniones realicemos, la paridad de las aristas se transporta de un líder a otro.

Damos la implementación del DSU que soporta paridad. Como en la sección anterior usamos un par para guardar el ancestro y la paridad. Además, para cada conjunto guardamos en el arreglo bipartite[] si sigue siendo bipartito o no.


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 (consulta de mínimo en un rango) offline en $O(\alpha(n))$ en promedio / truco de Arpa { #arpa data-toc-label=“RMQ offline / truco de Arpa”}

Se nos da un arreglo a[] y hay que calcular algunos mínimos en segmentos dados del arreglo.

La idea para resolver este problema con DSU es la siguiente: iteraremos sobre el arreglo y cuando estemos en el elemento i-ésimo responderemos todas las consultas (L, R) con R == i. Para hacer esto de forma eficiente mantendremos un DSU usando los primeros i elementos con la siguiente estructura: el padre de un elemento es el siguiente elemento más pequeño a su derecha. Entonces, usando esta estructura, la respuesta a una consulta será a[find_set(L)], el número más pequeño a la derecha de L.

Este enfoque obviamente solo funciona offline, es decir, si conocemos todas las consultas de antemano.

Es fácil ver que podemos aplicar compresión de caminos. Y también podemos usar unión por rango, si guardamos el líder real en un arreglo separado.


struct Query {
    int L, R, idx;
};
 
vector<int> answer;
vector<vector<Query>> container;

container[i] contiene todas las consultas con 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)];
    }
}

Hoy en día este algoritmo se conoce como el truco de Arpa (Arpa’s trick). Lleva el nombre de AmirReza Poorakhavan, que descubrió de forma independiente y popularizó esta técnica. Aunque este algoritmo ya existía antes de su descubrimiento.

LCA (ancestro común más bajo) offline en $O(\alpha(n))$ en promedio {data-toc-label=“LCA offline”}

El algoritmo para encontrar el LCA se discute en el artículo Ancestro común más bajo — algoritmo offline de Tarjan. Este algoritmo se compara favorablemente con otros algoritmos para encontrar el LCA debido a su simplicidad (especialmente comparado con un algoritmo óptimo como el de Farach-Colton and Bender).

Almacenar el DSU explícitamente como lista de conjuntos / Aplicaciones de esta idea al fusionar varias estructuras de datos

Una de las formas alternativas de almacenar el DSU es conservar cada conjunto en forma de una lista explícitamente almacenada de sus elementos. Al mismo tiempo, cada elemento también guarda la referencia al representante de su conjunto.

A primera vista esto parece una estructura de datos ineficiente: al combinar dos conjuntos tendremos que agregar una lista al final de la otra y actualizar el liderazgo en todos los elementos de una de las listas.

Sin embargo resulta que el uso de una heurística de pesos (similar a la unión por tamaño) puede reducir de forma significativa la complejidad asintótica: $O(m + n \log n)$ para realizar $m$ consultas sobre los $n$ elementos.

Por heurística de pesos entendemos que siempre agregaremos el más pequeño de los dos conjuntos al conjunto más grande. Agregar un conjunto a otro es fácil de implementar en union_sets y tomará un tiempo proporcional al tamaño del conjunto agregado. Y la búsqueda del líder en find_set tomará $O(1)$ con este método de almacenamiento.

Demostremos la complejidad temporal $O(m + n \log n)$ para la ejecución de $m$ consultas. Fijaremos un elemento arbitrario $x$ y contaremos cuántas veces se tocó en la operación de fusión union_sets. Cuando el elemento $x$ se toca por primera vez, el tamaño del conjunto nuevo será al menos $2$ . Cuando se toca por segunda vez, el conjunto resultante tendrá tamaño de al menos $4$ , porque el conjunto más pequeño se agrega al más grande. Y así sucesivamente. Esto significa que $x$ solo puede moverse en a lo sumo $\log n$ operaciones de fusión. Así, la suma sobre todos los vértices da $O(n \log n)$ más $O(1)$ por cada consulta.

Aquí hay una implementación:


vector<int> lst[MAXN];
int parent[MAXN];
 
void make_set(int v) {
    lst[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 (lst[a].size() < lst[b].size())
            swap(a, b);
        while (!lst[b].empty()) {
            int v = lst[b].back();
            lst[b].pop_back();
            parent[v] = a;
            lst[a].push_back (v);
        }
    }
}

Esta idea de agregar la parte más pequeña a una parte más grande también se puede usar en muchas soluciones que no tienen nada que ver con DSU.

Por ejemplo, consideremos el siguiente problema: se nos da un árbol, cada hoja tiene un número asignado (el mismo número puede aparecer varias veces en hojas distintas). Queremos calcular la cantidad de números distintos en el subárbol de cada nodo del árbol.

Aplicando a esta tarea la misma idea es posible obtener esta solución: podemos implementar un DFS que devolverá un puntero a un conjunto de enteros: la lista de números en ese subárbol. Luego, para obtener la respuesta del nodo actual (a menos que, por supuesto, sea una hoja), llamamos a DFS para todos los hijos de ese nodo, y fusionamos todos los conjuntos recibidos. El tamaño del conjunto resultante será la respuesta para el nodo actual. Para combinar de forma eficiente varios conjuntos simplemente aplicamos la receta descrita arriba: fusionamos los conjuntos agregando simplemente los más pequeños a los más grandes. Al final obtenemos una solución $O(n \log^2 n)$ , porque un número solo se agregará a un conjunto a lo sumo $O(\log n)$ veces.

Almacenar el DSU manteniendo una estructura de árbol explícita / Búsqueda de puentes online en $O(\alpha(n))$ en promedio {data-toc-label=“Almacenar el DSU manteniendo una estructura de árbol explícita / Búsqueda de puentes online”}

Una de las aplicaciones más potentes del DSU es que permite almacenar los conjuntos tanto como árboles comprimidos como no comprimidos. La forma comprimida se puede usar para fusionar árboles y para verificar si dos vértices están en el mismo árbol, y la forma no comprimida se puede usar —por ejemplo— para buscar caminos entre dos vértices dados, u otros recorridos de la estructura del árbol.

En la implementación esto significa que, además del arreglo comprimido de ancestros parent[], tendremos que mantener el arreglo de ancestros no comprimidos real_parent[]. Es trivial que mantener este arreglo adicional no empeorará la complejidad: los cambios en él solo ocurren cuando fusionamos dos árboles, y solo en un elemento.

Por otro lado, al aplicarlo en la práctica, a menudo hay que conectar árboles usando una arista especificada distinta de usar los dos nodos raíz. Esto significa que no queda otra opción que volver a enraizar uno de los árboles (hacer de los extremos de la arista la nueva raíz del árbol).

A primera vista parece que este re-enraizamiento es muy costoso y empeorará mucho la complejidad temporal. En efecto, para enraizar un árbol en el vértice $v$ hay que ir desde el vértice hasta la raíz antigua y cambiar las direcciones en parent[] y real_parent[] para todos los nodos de ese camino.

Sin embargo en realidad no es tan grave: podemos simplemente re-enraizar el más pequeño de los dos árboles, de forma similar a las ideas de las secciones anteriores, y obtener $O(\log n)$ en promedio.

Más detalles (incluida la demostración de la complejidad temporal) se pueden encontrar en el artículo Búsqueda de puentes online.

Retrospectiva histórica

La estructura de datos DSU se conoce desde hace mucho tiempo.

Esta forma de almacenar la estructura en forma de un bosque de árboles fue aparentemente descrita por primera vez por Galler y Fisher en 1964 (Galler, Fisher, “An Improved Equivalence Algorithm), sin embargo el análisis completo de la complejidad temporal se realizó mucho más tarde.

Las optimizaciones de compresión de caminos y unión por rango fueron desarrolladas por McIlroy y Morris, e independientemente de ellos también por Tritter.

Hopcroft y Ullman mostraron en 1973 la complejidad temporal $O(\log^\star n)$ (Hopcroft, Ullman “Set-merging algorithms”) — aquí $\log^\star$ es el logaritmo iterado (esta es una función de crecimiento lento, pero todavía no tan lenta como la función inversa de Ackermann).

Por primera vez la cota $O(\alpha(n))$ se mostró en 1975 (Tarjan “Efficiency of a Good But Not Linear Set Union Algorithm”). Más tarde, en 1985, él, junto con Leeuwen, publicó varios análisis de complejidad para distintas heurísticas de rango y formas de comprimir el camino (Tarjan, Leeuwen “Worst-case Analysis of Set Union Algorithms”).

Finalmente, en 1989 Fredman y Sachs demostraron que, en el modelo de cómputo adoptado, cualquier algoritmo para el problema de unión de conjuntos disjuntos tiene que trabajar en al menos $O(\alpha(n))$ de tiempo en promedio (Fredman, Saks, “The cell probe complexity of dynamic data structures”).