¿Qué es una estructura disjoint-set (union-find) con compresión de ruta y unión por rango?

Question

Accepted Answer

Una **disjoint-set** (union-find) rastrea elementos particionados en grupos no superpuestos y responde **"¿están estos dos en el mismo grupo?"** y **"fusionar dos grupos"** en **tiempo casi constante**. Con **compresión de ruta** y **unión por rango**, ambas operaciones se ejecutan en **O(α(n))** — efectivamente O(1) (α es la función inversa de Ackermann).

## Cómo funciona

Cada conjunto es un árbol; la **raíz** es el representante del conjunto. `find` camina hacia la raíz; `union` vincula una raíz bajo otra.

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## Code

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        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
```

| Operación | Tiempo (con ambas optimizaciones) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Usos comunes

- **MST de Kruskal** — fusionar componentes sin formar ciclos.
- **Componentes conectadas** en un grafo o cuadrícula.
- **Conectividad dinámica** y problemas de red/percolación.

## Por qué es importante

Union-find resuelve problemas de agrupación y conectividad que de otro modo requerirían recorridos de grafo O(n) repetidos, reduciéndolos a casi O(1) por consulta.

Es una herramienta estándar cuando debe fusionar conjuntos incrementalmente y probar la conectividad — un tema frecuente en entrevistas de nivel senior.