🧱 DSU (Union-Find)
Estructura de datos · Se implementa a mano · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras
📍 Dónde se aprende: módulo 19 de la Ruta de Aprendizaje.
El problema: saber si dos elementos ya están conectados
Tenemos seis computadoras, numeradas de 0 a 5. Al principio ninguna está conectada. Se añaden cables y queremos responder rápidamente si dos computadoras pertenecen al mismo grupo, incluso si están conectadas mediante otras.
Recorrer toda la red después de cada cable repite trabajo. DSU, también llamado Union-Find, mantiene una partición: cada elemento pertenece a un único conjunto. Sus operaciones son find(x), obtener el representante del conjunto, y unite(a,b), fusionar los conjuntos de a y b.
Representar un conjunto con un árbol de padres
Guardamos p[x], el padre de x. Un representante es una raíz cuyo padre es
él mismo. Seguir padres lleva hasta esa raíz. Dos elementos pertenecen al
mismo conjunto exactamente cuando llegan a la misma raíz.
Inicialmente p = [0,1,2,3,4,5]. Al unir 0 con 1 y 2 con 3 quedan raíces
0 y 2. Después unimos ambos grupos. Las flechas del dibujo apuntan al padre.
Si el diagrama no cabe, deslízalo horizontalmente.
| Operación | Cambio relevante | Conjuntos resultantes |
|---|---|---|
| Inicio | cada elemento es su propia raíz | {0}, {1}, {2}, {3}, {4}, {5} |
unite(0,1) | p[1] = 0 | {0,1}, {2}, {3}, {4}, {5} |
unite(2,3) | p[3] = 2 | {0,1}, {2,3}, {4}, {5} |
unite(0,2) | p[2] = 0 | {0,1,2,3}, {4}, {5} |
find(3) | recorrer 3→2→0 y guardar p[3] = 0 | los mismos conjuntos |
Estas flechas son una representación interna: no son necesariamente cables de la red original. DSU responde conectividad, no entrega el camino que une las computadoras ni su distancia.
Dos ideas para que los recorridos sean cortos
Unión por tamaño: al fusionar raíces, colgamos el conjunto menor de la
raíz del mayor. sz[raiz] guarda cuántos elementos contiene ese conjunto.
Si aumenta la profundidad de un elemento, el tamaño de su conjunto al menos
se duplica. Sin más mejoras, eso limita la profundidad a O(log n).
Compresión de caminos: después de encontrar una raíz, hacemos que cada
vértice del recorrido apunte directamente a ella. En el dibujo, find(3)
reemplaza 3→2→0 por 3→0. No cambia qué elementos están conectados, solo
acorta consultas futuras.
Juntas, estas técnicas dan costo O(α(n)) amortizado por operación, donde α es la inversa de Ackermann y crece extraordinariamente lento. «Amortizado» describe el promedio garantizado sobre una secuencia de operaciones, no que cada llamada individual haga exactamente la misma cantidad de trabajo.
Implementación y uso
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) { // true si fusionó dos conjuntos distintos
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b); // unión por tamaño
p[b] = a; sz[a] += sz[b];
return true;
}
};DSU d(6) crea los seis conjuntos. iota llena el arreglo de padres con
0,1,…,5. La expresión p[x] = find(p[x]) guarda la raíz encontrada y también
la devuelve; es la compresión escrita dentro de la función recursiva.
Después de ejecutar las tres uniones de la tabla:
d.find(1) == d.find(3)es verdadero.d.find(1) == d.find(4)es falso.d.unite(1,3)devuelvefalse: no fusionó dos grupos distintos.d.sz[d.find(3)]vale 4: consulta el tamaño en la raíz.
No leas sz[3] esperando el tamaño actual: los tamaños de nodos que dejaron
de ser raíces no se mantienen. Tampoco supongas que el representante será
siempre el menor elemento; depende de las uniones y los desempates.
El constructor cuesta O(n) y usa O(n) memoria. Los argumentos deben estar
entre 0 y n−1. El bloque requiere los encabezados de vector y iota
y el espacio de nombres estándar en el programa que lo use.
Qué garantiza una unión
Primero buscamos ambas raíces. Si son iguales, ya había conectividad y no cambiamos nada. Si son distintas, enlazar una raíz a la otra une dos árboles sin crear un ciclo de padres. Todos sus elementos pasan a alcanzar una raíz común.
La estructura admite añadir uniones, pero no deshacer una conexión arbitraria: perdió la información de qué cables eran esenciales. El DSU con rollback permite deshacer operaciones bajo otro diseño; no convierte esta versión en una estructura de borrado general.
¿Por qué unir dos elementos del mismo grupo no aumenta su tamaño?
Sus raíces ya son iguales. Sumarlas contaría dos veces los mismos elementos. El retorno temprano
falseconserva tanto el conjunto como su tamaño.
Es útil en conectividad incremental y en Kruskal (MST), que añade aristas solo cuando unen grupos distintos. Más práctica en 19 - Union-Find (DSU).