La gestión de colecciones de elementos que no se superponen, también conocidos como conjuntos disjuntos, es una tarea fundamental en muchos algoritmos de computación. Una de las estructuras de datos más eficientes para esta labor es la estructura Unión-Busca (Disjoint Set Union, DSU), también conocida como "Find-Union" o "Merge-Find". Sin embargo, antes de adentrarnos en DSU, es útil comprender el concepto subyacente a través de una técnica más elemental: el método de coloreado.

El Método de Coloreado

Imaginemos un problema en el que necesitamos determinar si dos individuos pertenecen al mismo grupo o familia (por ejemplo, el problema "P1551 - Familiares"). Una aproximación intuitiva sería asignar un "color" único a cada individuo inicialmente. Cuando se establece una relación (e.g., A y B son familiares), todos los individuos en el grupo de A y todos en el grupo de B deben ser "recoloreados" con el mismo color para reflejar su nueva unidad familiar.

La idea principal es que si dos elementos tienen el mismo color, pertenecen al mismo conjunto. Inicialmente, cada elemento tiene su propio color. Cuando dos elementos, A y B, se relacionan, se deben unificar sus colores, asignando un color común a todo el conjunto al que pertenecen A y B.

La implementación más directa de este enfoque implicaría recorrer y actualizar los colores de todos los elementos afectados en cada operación de unión. Esto puede llevar a una complejidad de tiempo de O(N) por operación en el peor de los casos, resultando en una complejidad total de O(N2) para N operaciones. Una pequeña optimización heurística podría ser siempre "colorear" el conjunto más pequeño con el color del más grande para reducir la cantidad de actualizaciones, pero la eficiencia sigue siendo un desafío.

Transición Hacia Unión-Busca

La limitación de rendimiento del método de coloreado nos lleva a una evolución conceptual: en lugar de cambiar los colores explícitamente, podemos hacer que un elemento "apunte" a otro, indicando que debe heredar su color (o, más precisamente, su identidad de conjunto). Si el elemento B apunta a A, B "debe ser" del color de A. Si C apunta a B, C "debe ser" del color de B, y por transitividad, del color de A. Esta cadena de punteros es, de hecho, la base de la estructura Unión-Busca.

Unión-Busca (DSU): Mantenimiento de la Transitividad

La estructura de datos Unión-Busca es altamente eficiente para tareas que requieren mantener colecciones de elementos disjuntos y determinar rápidamente si dos elementos pertenecen al mismo conjunto. Es especialmente útil cuando solo nos interesa la conectividad y no las relaciones jerárquicas o la distancia dentro de un grafo.

DSU se basa en la idea de representar cada conjunto mediante un "representante" o "líder". Cada elemento del conjunto apunta a su "padre", y el representante de un conjunto es el elemento que apunta a sí mismo (su propio padre).

Las dos operaciones fundamentales de DSU son:

1. Unir(x, y) (Merge/Union): Combina los conjuntos que contienen a los elementos x e y en un único conjunto.
2. Buscar(x) (Find): Retorna el representante (líder) del conjunto al que pertenece el elemento x. Con esta operación, podemos determinar si dos elementos x e y están en el mismo conjunto simplemente comparando Buscar(x) == Buscar(y).

Optimización 1: Compresión de Rutas

Una implementación ingenua de Buscar puede generar "árboles" muy profundos, haciendo que las búsquedas sean lentas (O(N) en el peor caso). La compresión de rutas es una técnica que aplana la estructura del árbol durante la operación Buscar. Cada vez que se busca el representante de un elemento, todos los nodos en la ruta desde ese elemento hasta la raíz se hacen hijos directos de la raíz. Esto mejora drásticamente el tiempo de futuras búsquedas.

Consideremos un arreglo global padre[] donde padre[i] almacena el padre del elemento i. Inicialmente, padre[i] = i para todos los elementos (cada uno es su propio representante).

int padre[MAX_ELEMENTOS]; // Arreglo para almacenar los padres de cada elemento

// Función para encontrar el representante de un elemento con compresión de rutas
int encontrarRepresentante(int elemento) {
    if (padre[elemento] == elemento) { // Si el elemento es su propio padre, es el representante
        return elemento;
    }
    // Si no, asignamos directamente la raíz encontrada a todos los nodos en el camino
    return padre[elemento] = encontrarRepresentante(padre[elemento]);
}

// Función para unir dos conjuntos
void fusionarConjuntos(int elemA, int elemB) {
    int raizA = encontrarRepresentante(elemA);
    int raizB = encontrarRepresentante(elemB);
    if (raizA != raizB) { // Si ya no están en el mismo conjunto
        padre[raizA] = raizB; // Se une la raíz de A a la raíz de B
    }
}

Optimización 2: Unión por Rango o Tamaño

Además de la compresión de rutas, otra optimización crucial es la unión por rango (o por altura del árbol) o unión por tamaño (o por número de elementos en el conjunto). Cuando se unen dos conjuntos, se adjunta la raíz del árbol más pequeño a la raíz del árbol más grande. Esto evita que los árboles se desequilibren excesivamente, manteniendo su altura lo más pequeña posible.

La combinación de compresión de rutas y unión por rango/tamaño hace que las operaciones de DSU sean casi constantes en tiempo, con una complejidad amortizada de O(α(N)) para cada operación, donde α es la función inversa de Ackermann, que crece extremadamente lento (para cualquier N práctico, α(N) ≤ 4 o 5).

Para la unión por tamaño, necesitamos un arreglo adicional tamañoConjunto[] que almacene el número de elementos en el conjunto representado por cada raíz.

int padre[MAX_ELEMENTOS];
int tamañoConjunto[MAX_ELEMENTOS]; // Almacena el tamaño del conjunto si es una raíz

// Función para encontrar el representante sin compresión de rutas (si se usa unión por rango/tamaño puro)
// Aunque usualmente se combinan ambas optimizaciones, aquí mostramos la idea
int buscarLider(int nodo) {
    if (padre[nodo] == nodo) {
        return nodo;
    }
    // Si queremos compresión de rutas, sería: return padre[nodo] = buscarLider(padre[nodo]);
    return buscarLider(padre[nodo]); // Sin compresión, solo para demostrar la unión por tamaño
}

// Función para fusionar conjuntos utilizando la heurística de tamaño
void unirPorTamaño(int elem1, int elem2) {
    int lider1 = buscarLider(elem1);
    int lider2 = buscarLider(elem2);

    if (lider1 != lider2) {
        // Aseguramos que lider1 sea el representante del conjunto más grande
        if (tamañoConjunto[lider1] < tamañoConjunto[lider2]) {
            std::swap(lider1, lider2); // Intercambiamos para que lider1 sea el más grande
        }
        padre[lider2] = lider1; // El conjunto más pequeño se adjunta al más grande
        tamañoConjunto[lider1] += tamañoConjunto[lider2]; // Actualizamos el tamaño del conjunto resultante
    }
}

Comparación de Enfoques

• Compresión de Rutas: Es fácil de implementar y muy efectiva. Sin embargo, modifica la estructura original del árbol, lo cual podría ser una desventaja en problemas donde la estructura exacta del árbol (e.g., para arrays persistentes o consultas de profundidad) es relevante.
• Unión por Rango/Tamaño: Preserva mejor la estructura relativa del árbol y garantiza una altura logarítmica para los árboles. En el peor caso, su complejidad es asintóticamente superior a la compresión de rutas pura, pero combinadas ofrecen el rendimiento óptimo. Es ligeramente más compleja de codificar.

En la práctica, la combinación de ambas optimizaciones (compresión de rutas y unión por tamaño/rango) es la más común y recomendada para la mayoría de las aplicaciones de DSU, ya que proporciona la mejor eficiencia posible.

Aplicaciones Comunes

La estructura Unión-Busca tiene múltiples aplicaciones en problemas de grafos y conectividad:

• Conectividad en Grafos: Determinar si dos nodos están conectados o ecnontrar los componentes conectados de un grafo.
• Algoritmo de Kruskal: Utilizado para encontrar el Árbol de Expansión Mínimo (MST) de un grafo.
• Mantenimiento de Relaciones Complejas: Versiones extendidas de DSU (DSU con "dominio extendido" o "DSU con pesos") pueden modelar relaciones más intrincadas, como "el enemigo de mi enemigo es mi amigo", manteniendo estados o pesos asociados a las uniones.

Ejemplo: Problema de Conectividad Geométrico (Adaptación de P3958)

Consideremos un problema donde tenemos un bloque de queso de una altura H y un radio R. Hay N perforaciones cilíndricas en el queso, cada una con un radio R. Queremos saber si un ratón puede pasar de la superficie superior a la inferior. Dos perforaciones se consideran conectadas si sus esferas de influencia (centros + radio R) se tocan o superponen. Las perforaciones también pueden tocar la superficie superior o inferior.

Este problema se puede resolver eficazmente con DSU. Creamos N elementos para las perforaciones y dos nodos "virtuales": uno para la superficie superior y otro para la inferior. Luego, unimos los conjuntos:

1. Inicializamos DSU para N perforaciones y los 2 nodos virtuales (e.g., N para la superficie inferior y N+1 para la superior).
2. Para cada perforación, verificamos si toca la superficie superior o inferior y unimos su conjunto con el nodo virtual correspondiente.
3. Para cada par de perforaciones, calculamos la distancia entre sus centros. Si es menor o igual a 2R, significa que se tocan, y unimos sus conjuntos.
4. Finalmente, comprobamos si los nodos virtuales de la superficie superior e inferior pertenecen al mismo conjunto. Si es así, hay un camino.

Para evitar problemas de precisión con la función sqrt() al calcular distancias, es mejor comparar la distancia al cuadrado. Si la distancia entre dos centros es d, y se tocan si d <= 2R, entonces d^2 <= (2R)^2. La distancia al cuadrado entre dos puntos (x1, y1, z1) y (x2, y2, z2) es (x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2.

// Estructura para DSU struct DSU { std::vector parent; // std::vector ranks; // Podríamos usar rangos también

DSU(int n) {
    parent.resize(n);
    std::iota(parent.begin(), parent.end(), 0); // Inicializa parent[i] = i
    // ranks.assign(n, 0); // Inicializa rangos a 0
}

int find(int i) {
    if (parent[i] == i)
        return i;
    return parent[i] = find(parent[i]); // Compresión de rutas
}

void unite(int i, int j) {
    int root_i = find(i);
    int root_j = find(j);
    if (root_i != root_j) {
        // Unir por rango o simplemente uno al otro
        parent[root_i] = root_j; // Unir el conjunto de i al conjunto de j
    }
}

};

// Estructura para almacenar las coordenadas de una perforación struct Perforacion { long long x, y, z; };

// Función principal del problema adaptado void resolverProblemaQueso(int numPerforaciones, long long radioPerforacion, long long alturaTotal) { // numPerforaciones + 2 para los nodos virtuales: // - numPerforaciones: Representa la superficie inferior virtual // - numPerforaciones + 1: Representa la superficie superior virtual DSU dsu(numPerforaciones + 2); std::vector<Perforacion> perforaciones(numPerforaciones);

for (int i = 0; i < numPerforaciones; ++i) {
    std::cin >> perforaciones[i].x >> perforaciones[i].y >> perforaciones[i].z;

    // Verificar conectividad con la superficie superior virtual
    if (perforaciones[i].z + radioPerforacion >= alturaTotal) {
        dsu.unite(i, numPerforaciones + 1); // Unir perforación 'i' con superficie superior
    }
    // Verificar conectividad con la superficie inferior virtual
    if (perforaciones[i].z - radioPerforacion <= 0) {
        dsu.unite(i, numPerforaciones); // Unir perforación 'i' con superficie inferior
    }

    // Verificar conectividad con perforaciones anteriores
    for (int j = 0; j < i; ++j) {
        long long dx = perforaciones[i].x - perforaciones[j].x;
        long long dy = perforaciones[i].y - perforaciones[j].y;
        long long dz = perforaciones[i].z - perforaciones[j].z;
        long long distanciaCuadrada = dx*dx + dy*dy + dz*dz;

        // Las perforaciones se conectan si sus centros están a una distancia <= 2*radioPerforacion
        if (distanciaCuadrada <= 4LL * radioPerforacion * radioPerforacion) { // (2R)^2
            dsu.unite(i, j);
        }
    }
}

// Comprobar si las superficies superior e inferior están conectadas
if (dsu.find(numPerforaciones) == dsu.find(numPerforaciones + 1)) {
    std::cout << "Si" << std::endl;
} else {
    std::cout << "No" << std::endl;
}

}

</details>### Unión-Busca Ponderada

Una extensión más avanzada de DSU es la "Unión-Busca Ponderada" (Weighted DSU). Esta versión no solo mantiene los conjuntos, sino que también almacena información adicional o "pesos" en cada nodo, que representan la relación del nodo con su padre o con la raíz de su componente. Estos pesos pueden ser distancias, diferencias, o cualquier otra métrica. Durante la compresión de rutas y las uniones, estos pesos se actualizan de manera consistente, a menudo mediante el uso de operaciones de "suma de prefijos" o composición de relaciones, permitiendo consultas más complejas sobre los elementos dentro de un mismo conjunto.