1. Conceptos Básicos

Un conjunto disjunto es una colección de conjuntos mutuamente excluyentes. Las operaciones principales son:

• find(x): devuelve el representante (raíz) del conjunto que contiene a x.
• union(x, y): combina los conjuntos que contienen a x y y.

Sin optimizaciones, ambas operaciones pueden ser O(n). Con Path Compression y Union by Rank/Size la complejidad amortizada es O(α(n)), donde α es la inversa de la función de Ackermann, prácticamente constante para cualquier n razonable.

2. Implementación Clásica en Python

Comenzaremos con una versión mínima, seguida de la versión optimizada.

2.1 Versión Básica (Sin Compresión)

class DisjointSetBasic:
    def __init__(self, elements=None):
        """Crea un conjunto disjunto donde cada elemento es su propio padre."""
        self.parent = {}
        if elements:
            for e in elements:
                self.parent[e] = e
    def find(self, x):
        """Devuelve la raíz de x recorriendo los padres."""
        while self.parent[x] != x:
            x = self.parent[x]
        return x
    def union(self, x, y):
        """Une los conjuntos que contienen a x y a y."""
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

Esta versión funciona, pero find puede llegar a ser lineal en el peor caso.

2.2 Versión Optimizada (Path Compression + Union by Rank)

class DisjointSet:
    """Implementación de Union‑Find con compresión de caminos y unión por rango.
    Compatibilidad: Python 3.8+ (type hints opcionales).
    """
    def __init__(self, elements: list | None = None):
        self.parent: dict = {}
        self.rank: dict = {}
        if elements:
            for e in elements:
                self.parent[e] = e
                self.rank[e] = 0
    def make_set(self, x) -> None:
        """Añade un nuevo elemento aislado al conjunto."""
        self.parent[x] = x
        self.rank[x] = 0
    def find(self, x):
        """Encuentra la raíz de x aplicando path compression recursiva.
        Complejidad amortizada: O(α(n)).
        """
        if self.parent[x] != x:
            # compresión de camino: asignamos directamente la raíz
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y) -> bool:
        """Une los conjuntos de x e y usando union by rank.
        Devuelve True si se realizó una unión, False si ya estaban en el mismo conjunto.
        """
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        # unión por rango (rank)
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

Esta clase es la base para la mayoría de los algoritmos de grafos que requieren gestión de componentes.

3. Casos de Uso Reales

A continuación, vemos tres aplicaciones prácticas donde Union‑Find brilla.

3.1 Algoritmo de Kruskal (MST)

def kruskal_mst(vertices: list, edges: list) -> list:
    """Construye el árbol de expansión mínima usando Kruskal.
    * vertices – lista de nodos.
    * edges – lista de tuplas (peso, u, v).
    """
    # ordenar aristas por peso ascendente
    edges.sort(key=lambda e: e[0])
    ds = DisjointSet(vertices)
    mst = []
    for w, u, v in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, w))
    return mst
# Ejemplo rápido
vertices = ['A', 'B', 'C', 'D']
edges = [
    (1, 'A', 'B'),
    (3, 'A', 'C'),
    (2, 'B', 'C'),
    (4, 'B', 'D'),
    (5, 'C', 'D')
]
print(kruskal_mst(vertices, edges))

El algoritmo corre en O(E log E) por la ordenación, mientras que las operaciones Union‑Find son prácticamente O(1).

3.2 Detección de Ciclos en Grafos No Dirigidos

def tiene_ciclo(edges: list) -> bool:
    """Devuelve True si el grafo contiene al menos un ciclo.
    Cada arista se representa como (u, v).
    """
    ds = DisjointSet()
    for u, v in edges:
        if ds.find(u) == ds.find(v):
            return True  # arista forma un ciclo
        ds.union(u, v)
    return False
print(tiene_ciclo([('A','B'),('B','C'),('C','A')]))  # True
print(tiene_ciclo([('A','B'),('B','C'),('C','D')]))  # False

3.3 Problema de “Friend Circles” (LeetCode 547)

def find_circle_num(M):
    """M es una matriz de adyacencia donde M[i][j] == 1 indica amistad.
    Devuelve el número de círculos de amistad.
    """
    n = len(M)
    ds = DisjointSet([i for i in range(n)])
    for i in range(n):
        for j in range(i + 1, n):
            if M[i][j] == 1:
                ds.union(i, j)
    # Contar raíces distintas
    return len({ds.find(i) for i in range(n)})

4. Comparativa con Otras Aproximaciones

En la práctica, Union‑Find domina cuando el número de operaciones union/find supera en gran medida la cantidad de nodos.

5. Buenas Prácticas y Optimización

• Inicializa siempre con make_set o constructor: evita KeyError al usar elementos no registrados.
• Usa union by size en lugar de rank si prefieres mantener un contador de tamaño; la lógica es idéntica.
• Evita recursión profunda en find cuando el árbol está muy desequilibrado (aunque la compresión lo mitiga). Si tu entorno tiene límite bajo de recursión, implementa una versión iterativa:

def find_iterative(self, x):
    root = x
    while self.parent[root] != root:
        root = self.parent[root]
    # compresión de camino iterativa
    while x != root:
        parent = self.parent[x]
        self.parent[x] = root
        x = parent
    return root

Esta variante es segura para entornos con sys.setrecursionlimit bajo.

Otros tips:

• Si trabajas con big data (millones de elementos), considera usar array('I') o numpy.ndarray para almacenar parent y rank y reducir la sobrecarga de objetos Python.
• Para entornos multihilo, protege union y find con threading.Lock o emplea versiones lock‑free basadas en atomic (disponibles en Cython).
• En algoritmos distribuidos, mira Union‑Find paralelo (algoritmo de Shiloach‑Vishkin) que combina compresión de caminos con procesamiento en GPU.

6. Depuración y Troubleshooting

Los errores más comunes aparecen por:

1. Elementos no registrados: lanzar KeyError al hacer find. Solución: llama a make_set antes de cualquier operación o usa defaultdict(lambda: x) con lógica personalizada.
2. Recursión infinita si parent[x] = x nunca se establece para algún nodo. Verifica la inicialización.
3. Fugas de memoria al mantener referencias a objetos pesados dentro de los nodos. Mantén los valores simples (int, str) o usa IDs numéricos.

Ejemplo de mensaje de depuración útil:

def find(self, x):
    if x not in self.parent:
        raise ValueError(f"Elemento {x!r} no pertenece al conjunto")
    # resto del algoritmo ...

Usa logging en modo DEBUG para rastrear la evolución de los padres:

import logging
logging.basicConfig(level=logging.DEBUG)
logger = logging.getLogger(__name__)
def union(self, x, y):
    logger.debug("Union %s - %s", x, y)
    # ... código ...
    logger.debug("Parents after union: %s", self.parent)

7. Compatibilidad, Rendimiento y Escalabilidad

Compatibilidad: La clase presentada funciona en Python 3.8+, pero no depende de características específicas, por lo que también es válida en 3.6+. Si deseas usar type hints más avanzados (e.g., list[int]) puedes requerir 3.9+.

Rendimiento (benchmark rápido):

import time, random
N = 1_000_000
uf = DisjointSet([i for i in range(N)])
start = time.time()
for _ in range(N):
    a, b = random.randint(0, N-1), random.randint(0, N-1)
    uf.union(a, b)
print('Tiempo union (1M ops):', time.time() - start)

En una máquina típica (Intel i7) el tiempo está alrededor de 0.6‑0.9 s, demostrando la eficiencia de la estructura.

Escalabilidad: Para volúmenes > 10⁸, la limitación pasa a la gestión de memoria de Python. En esos casos, migrar a una implementación en C/C++ (p.ej., Boost.UnionFind) o usar numpy.ndarray como backend puede reducir la huella a para 100 M elementos.

8. Conclusión

Los Conjuntos Disjuntos son una herramienta esencial para cualquier ingeniero de software que trabaje con grafos, clustering o problemas de conectividad. Con la combinación de Path Compression y Union by Rank/Size obtienes una estructura prácticamente constante en tiempo, adecuada tanto para prototipos en Python como para sistemas de producción de gran escala.

Aplica los patrones mostrados, sigue las buenas prácticas de inicialización y depuración, y adapta la implementación a tu stack (numpy, Cython, o paralelismo) para sacarle el máximo provecho.