Union-find (conjuntos disjuntos) explicado: cómo funciona, código y complejidad

Qué problema resuelve union-find

Imagina una red de computadoras a la que se añaden cables uno a uno, y tras cada cable debes responder "¿están conectadas la computadora A y la B?". Ejecutar una búsqueda en el grafo para cada pregunta cuesta O(n + m) cada vez. Union-find responde cada pregunta en casi O(1) manteniendo los grupos conectados a medida que se añaden cables.

La misma necesidad aparece en el algoritmo de Kruskal para el árbol de expansión mínima (¿estos dos extremos ya pertenecen al mismo árbol?), en la detección de ciclos en un grafo no dirigido, al agrupar cuentas que comparten un correo electrónico, en simulaciones de percolación y en procesamiento de imágenes para etiquetar regiones conexas.

La idea en palabras sencillas

Cada elemento apunta a un padre. Un elemento que apunta a sí mismo es una raíz, y la raíz es el representante de todo el grupo. Para hallar el grupo de x, sigue los punteros al padre hasta llegar a una raíz. Para fusionar dos grupos, encuentra ambas raíces y haz que una apunte a la otra.

Dos optimizaciones mantienen los árboles planos:

• Unión por rango (o por tamaño): cuelga el árbol más bajo (o más pequeño) del más alto (o más grande), de modo que la altura solo crece cuando se fusionan dos árboles iguales.
• Compresión de caminos: durante find, haz que cada nodo del camino apunte directamente a la raíz, de modo que la siguiente búsqueda sea de un paso.

Ejemplo resuelto: cinco elementos

Empieza con los elementos 0 a 4, cada uno en su propio grupo. El arreglo de padres es [0, 1, 2, 3, 4]. Usamos unión por tamaño y, cuando los tamaños son iguales, la segunda raíz pasa a ser la hija.

Implementación en Python

Esta versión usa unión por tamaño y un find iterativo con compresión de caminos, así que no tiene problemas de profundidad de recursión. union devuelve False cuando los dos elementos ya estaban en el mismo grupo, lo que es útil para detectar ciclos.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:       # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                 # ra is the larger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.find(3), uf.parent)       # 0 [0, 0, 0, 0, 4]
print(uf.connected(1, 4), uf.groups)  # False 2

Ejemplo: detectar un ciclo en un grafo no dirigido

Procesa las aristas una a una. Si ambos extremos de una arista ya tienen la misma raíz, esa arista cierra un ciclo. El algoritmo de Kruskal usa exactamente esta comprobación tras ordenar las aristas por peso.

def has_cycle(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return True
    return False

print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))  # False
print(has_cycle(4, [(0, 1), (1, 2), (2, 0)]))  # True

Complejidad temporal y espacial

α(n) es la inversa de la función de Ackermann, que crece tan despacio que vale como máximo 4 para cualquier n que quepa en una computadora real. En la práctica esto significa tiempo constante por operación. Robert Tarjan demostró esta cota en 1975. El espacio es O(n) para los arreglos de padres y de tamaños.

Variantes y errores comunes

• Comparar elementos en lugar de raíces: union debe enlazar find(a) y find(b), no a y b directamente.
• Suponer que parent[x] es el representante. Tras varias uniones, solo find(x) es correcto; llama a find con cada elemento antes de agrupar por padre.
• Un find recursivo con entradas grandes y sin unión por rango puede alcanzar el límite de recursión de Python; la versión iterativa de arriba lo evita.
• Elementos que no son enteros de 0 a n-1: asígnalos primero a índices con un dict, o guarda los padres en un dict y añade los elementos de forma perezosa.
• Union-find no puede dividir grupos. Si se eliminan aristas, necesitas otra estructura o un enfoque offline que procese las eliminaciones en orden inverso.
• El union-find ponderado guarda en cada nodo un desplazamiento respecto a su padre, lo que responde preguntas como "¿cuánto más pesado es a que b?".

Cuándo usarlo y problemas típicos

Usa union-find cuando los grupos solo se fusionan y necesitas preguntar si dos elementos están en el mismo grupo, o cuántos grupos hay. Para una sola pregunta de conectividad en un grafo estático, un BFS o DFS simple es más sencillo. Cuando necesites caminos reales, usa búsqueda en grafos, porque union-find solo conoce la pertenencia.

Problemas típicos: número de componentes conexas, número de islas (con las celdas de la cuadrícula como elementos), conexión redundante (la arista que crea un ciclo), fusión de cuentas, satisfacibilidad de ecuaciones de igualdad como a == b, b != c y el árbol de expansión mínima de Kruskal.