Union-Find (Conjuntos Disjuntos) Explicado, con Código

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

¿Qué Es Union-Find?

Union-find, también llamado disjoint set union (DSU), es una estructura de datos que rastrea un conjunto de elementos divididos en grupos que no se solapan. Cada elemento pertenece exactamente a un grupo, y cada grupo se identifica por un único representante, su raíz.

El truco está en cómo se almacenan los grupos: como un bosque de árboles. Cada elemento tiene un puntero al padre, y seguir a los padres hacia arriba siempre lleva a la raíz del grupo. Dos elementos están en el mismo grupo si y solo si comparten la misma raíz. Esa es toda la idea, y todo lo demás consiste en hacerla rápida.

Las Dos Operaciones

Union-find admite exactamente dos operaciones, y toda su reputación descansa en hacer ambas casi al instante.

• find(x) devuelve la raíz del grupo que contiene a x, subiendo por los punteros al padre. Dos elementos están conectados cuando find(a) == find(b).
• union(a, b) fusiona los dos grupos haciendo que una raíz sea el padre de la otra.

Como los grupos solo se fusionan y nunca se dividen, union-find es perfecto para problemas donde las conexiones se añaden con el tiempo pero nunca se eliminan.

La Versión Ingenua y Su Problema

Un primer intento solo guarda punteros al padre y fusiona apuntando una raíz a la otra. Funciona, pero tiene un fallo desagradable: nada impide que los árboles crezcan hasta ser cadenas largas. Si cada unión apila un nodo sobre el último, find tiene que recorrer una cadena de longitud n, y cada operación se degrada a O(n).

Eso no es mejor que una lista simple. La solución son dos pequeños cambios que, juntos, son uno de los resultados más célebres en estructuras de datos.

Dos Optimizaciones Que lo Cambian Todo

La unión por rango mantiene los árboles poco profundos. Al fusionar dos grupos, cuelga siempre el árbol más corto bajo la raíz del más alto. Un árbol corto colgado de uno alto no aumenta la altura, así que los árboles se mantienen planos.

La compresión de caminos aplana sobre la marcha. Cada vez que find sube hasta una raíz, vuelve a apuntar cada nodo por el que pasó directamente a esa raíz. El siguiente find sobre cualquiera de ellos es entonces un solo salto. La figura de abajo muestra un find colapsando una cadena.

Usadas juntas, la unión por rango y la compresión de caminos mantienen cada árbol casi completamente plano, así que ambas operaciones se ejecutan en tiempo casi constante. Cualquiera por sí sola ayuda; las dos juntas son lo que hace famoso a union-find.

Implementación en Python

Toda la estructura cabe en una clase pequeña. Dos arreglos hacen todo el trabajo: parent y rank.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # cada elemento empieza siendo su propia raíz
        self.rank = [0] * n            # una cota superior de la altura de cada árbol

    def find(self, x):
        # Compresión de caminos: apunta x directamente a la raíz.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # ya en el mismo grupo

        # Unión por rango: cuelga el árbol más corto bajo el más alto.
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

Fíjate en que union devuelve False cuando los dos elementos ya estaban conectados. Ese único booleano es lo que hace tan limpias la detección de ciclos y el algoritmo de Kruskal: si una unión falla, la arista que ibas a añadir habría cerrado un ciclo.

Complejidad: Casi Constante

Con ambas optimizaciones, una secuencia de m operaciones sobre n elementos se ejecuta en O(m · α(n)) en total, donde α es la función inversa de Ackermann.

La función inversa de Ackermann crece tan despacio que α(n) es como mucho 4 para cualquier n que quepa en el universo observable. En la práctica, trata cada operación como tiempo constante. Para ver cómo encaja entre todos los algoritmos de grafos, consulta la guía de complejidad y la chuleta.

Dónde Se Usa

Union-find aparece siempre que necesitas rastrear la conectividad a medida que crece.

• Árbol de expansión mínima de Kruskal: ordena las aristas y luego añade cada una solo si sus extremos están en grupos distintos. Union-find es la comprobación de ciclos. Consulta árboles de expansión mínima.
• Detección de ciclos en un grafo no dirigido: para cada arista, si ambos extremos ya comparten una raíz, la arista cierra un ciclo.
• Componentes conexas: une cada arista y luego cuenta las raíces distintas.
• Conectividad dinámica y entrevistas: problemas como Number of Provinces, Redundant Connection y Accounts Merge son todos union-find disfrazado. Consulta algoritmos de grafos para entrevistas de programación.

También está en la Etapa 3 de la hoja de ruta de teoría de grafos, justo donde aprendes los árboles de expansión.