Union-Find (también llamado Disjoint Set Union, DSU) mantiene una partición de elementos en conjuntos disjuntos, soportando dos operaciones:

• Find(x): determina el conjunto al que pertenece x (usualmente retorna el representante/root).
• Union(x, y): fusiona los conjuntos que contienen x e y.

Es uno de los datos structures más útiles en teoría de grafos, especialmente para Kruskal’s MST, detectar ciclos, y conectividad dinámica.

Cómo Funciona

Sin optimización (naive)

Array parent[] donde parent[i] es el padre de i en un árbol.

• Find: sigue parent hasta llegar a la raíz (parent[root] = root).
• Union: hace parent[root_x] = root_y.

Con path compression + union by rank

• Path compression: durante find, haz parent[i] = root para todos los nodos en el camino.
• Union by rank: siempre adjunta el árbol más pequeño bajo la raíz del más grande.

Idea Clave

Path compression aplana el árbol: después de un find, todos los nodos en el camino apuntan directamente a la raíz. Eso reduce la altura del árbol a casi constante.

Union by rank previene árboles altos: siempre fusionas el árbol más pequeño bajo el más grande, manteniendo altura ≤ O(log n).

Juntas, logran O(α(n)) amortizado, donde α es la inversa de Ackermann (prácticamente ≤ 5 para cualquier n realista).

Ejemplo Trabajado

Elementos {0,1,2,3,4}. Operaciones:

1. Union(0,1): parent[0]=1 (rank[1]=1).
2. Union(2,3): parent[2]=3 (rank[3]=1).
3. Union(1,2): parent[3]=1 (rank[1]=2).
   • Árbol: 1 es raíz, hijos 0 y 3; 3 tiene hijo 2.
4. Find(2): 2→3→1. Con path compression: parent[2]=1, parent[3]=1.
5. Union(4,3): parent[4]=1 (rank[1]=2).
6. Find(4): 4→1, raíz = 1.

Resultado: un solo conjunto {0,1,2,3,4} con raíz 1.

Casos Extremos y Trampas

• Union sin rank — árbol degenerado en línea: O(n) por operación.
• Path compression sola — mejora pero sin rank puede ser O(log n).
• Solo rank — mejor que naive pero sin compression es O(log n).
• Ambas optimizaciones — O(α(n)) amortizado, prácticamente constante.

Comparación

Aplicaciones

• Kruskal’s MST — detectar ciclos en O(E α(V))
• Conectividad dinámica — componentes conexos en grafos cambiantes
• Imagen processing — connected components en píxeles
• Enseñanza — ejemplo de optimizaciones que transforman O(n) en O(α(n))

Trayectoria de Práctica

1. Implementa DSU naive; prueba con 1000 unions.
2. Añade union by rank; mide la diferencia.
3. Añade path compression; verifica que es prácticamente constante.
4. Implementa Kruskal usando DSU.
5. Investiga offline dynamic connectivity: ¿cómo manejar borrados?