🧱 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.

01230123Antes de find(3)Después de find(3)Mismo conjunto {0,1,2,3}; 4 y 5 siguen separados (no dibujados)

Si el diagrama no cabe, deslízalo horizontalmente.

OperaciónCambio relevanteConjuntos resultantes
Iniciocada 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] = 0los 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) devuelve false: 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.

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).