DSU con compresión de caminos
Implemente find con compresión de caminos para que todos los nodos del camino apunten directamente a la raíz, logrando un coste amortizado de find cercano a O(1).
DSU con compresión de caminos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué es Disjoint Set Union?
Disjoint Set Union (DSU), también conocido como Union-Find, es una estructura de datos que mantiene una colección de conjuntos disjuntos (sin elementos comunes). Admite dos operaciones principales: find (¿a qué conjunto pertenece el elemento x?) y union (fusionar los conjuntos que contienen x e y). DSU es ideal para problemas de conectividad dinámica en los que los grupos se fusionan con el tiempo, pero nunca se dividen.
Cada elemento comienza en su propio conjunto. A medida que procesamos aristas o relaciones, fusionamos conjuntos. El reto consiste en hacerlo de forma eficiente: las implementaciones ingenuas cuestan O(n) por operación, pero con optimizaciones nos acercamos a O(1) amortizado.
# Naive DSU without optimisations
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # each node is its own parent
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = pyEl problema de un find ingenuo
En el DSU ingenuo, find(x) recorre la cadena de padres hacia arriba hasta llegar a un nodo que apunta a sí mismo (la raíz). Si el árbol está equilibrado, esto cuesta O(log n). Sin embargo, si siempre unimos enlazando la segunda raíz debajo de la primera, podemos crear una cadena (un árbol degenerado) de longitud n, lo que hace que cada operación find cueste O(n).
Considere unir 0→1→2→3→4 en secuencia. La llamada a find del nodo 0 debe recorrer toda la cadena. Con la compresión de caminos, eliminamos este problema haciendo que cada nodo visitado apunte directamente a la raíz durante la propia operación find.
# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4] => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4] => find(0) takes 1 step
parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
x = parent[x]
steps += 1
print('Root:', x, 'Steps taken:', steps)Compresión de caminos: recursiva en una pasada
La compresión de caminos modifica la operación find de modo que, después de encontrar la raíz, cada nodo del camino se actualiza para apuntar directamente a ella. Las futuras llamadas a find sobre esos nodos cuestan O(1). La versión recursiva logra esto de forma elegante en una sola pasada.
La idea clave es la siguiente: cuando la llamada recursiva devuelve la raíz, establecemos self.parent[x] = root antes de devolverla. Esto aplana el árbol: ahora todos los nodos del camino de búsqueda apuntan directamente a la raíz. Esto no cambia el conjunto al que pertenece un nodo; solo acorta los caminos de búsqueda futuros.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)Compresión de caminos: iterativa en dos pasadas
La versión iterativa de la compresión de caminos utiliza dos pasadas: en la primera, recorre el camino hacia arriba para encontrar la raíz; en la segunda, vuelve a visitar cada nodo del camino y actualiza su padre para que apunte directamente a la raíz. Esto evita la sobrecarga de la pila de recursión y es seguro para árboles muy profundos, cercanos al límite de recursión de Python.
Tanto en el enfoque recursivo como en el iterativo, la corrección no cambia: find sigue devolviendo la misma raíz. La única diferencia es que los punteros a los padres se actualizan como efecto secundario, lo que hace que todas las futuras llamadas a find sobre esos nodos cuesten O(1).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root] # first pass: find root
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root # second pass: compress
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
return True
return False # already connected
dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after find(0):', dsu.parent[:])Complejidad amortizada de la compresión de caminos
La compresión de caminos por sí sola logra un tiempo amortizado de O(log n) por operación en una secuencia de m operaciones. Cada operación find puede ser costosa la primera vez que se recorre una cadena, pero aplana esa cadena, de modo que cada find posterior sobre esos nodos cuesta O(1). El trabajo total se distribuye entre muchas operaciones.
El análisis formal utiliza el método de la función potencial: el potencial del DSU disminuye cada vez que se acorta el padre de un nodo, y esta disminución compensa el coste del recorrido. Sin union by rank, la compresión de caminos por sí sola proporciona O(log n) amortizado, una mejora enorme frente al O(n) ingenuo.
# Demonstrating amortised benefit
import time
def build_chain(n):
parent = list(range(n))
for i in range(n - 1):
parent[i] = i + 1 # chain: 0->1->2->...->n-1
return parent
n = 1000
parent = build_chain(n)
# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
root = parent[root]
# Compress
while parent[x] != root:
nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0]) # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')Conteo de componentes conexas
Una aplicación común del DSU es contar las componentes conexas de un grafo. Inicializamos un contador components igual a n (uno por nodo). Cada union exitosa (que fusiona dos conjuntos distintos) decrementa el contador en 1. Al final, el contador contiene el número de componentes distintas.
Esto es más eficiente que ejecutar BFS o DFS para consultar la conectividad, especialmente cuando las aristas llegan de forma incremental (en línea). El DSU procesa cada arista en un tiempo amortizado cercano a O(1), independientemente del momento en que llegue.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
self.parent[px] = py
self.components -= 1
return True
dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
dsu.union(u, v)
print('Components:', dsu.components) # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')DSU para problemas de grafos: número de provincias
El problema Number of Provinces proporciona una matriz de adyacencia n×n y pregunta cuántos grupos de ciudades conectadas directa o indirectamente existen. Es exactamente un problema de componentes conexas que el DSU resuelve de forma sencilla. Recorremos todos los pares (i, j) para los que isConnected[i][j] == 1 y llamamos a union(i, j).
Después de procesar todas las conexiones, dsu.components contiene la respuesta. Esto es más sencillo y rápido que ejecutar BFS desde cada nodo no visitado, y permite trabajar directamente con la representación matricial sin construir antes una lista de adyacencia.
def find_provinces(isConnected):
n = len(isConnected)
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py:
parent[px] = py
return True
return False
count = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
if union(i, j):
count -= 1
return count
matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix)) # 2: cities {0,1} and {2}Variantes de la compresión de caminos: reducción a la mitad
Además de la compresión en dos pasadas, existe una variante más sencilla en una pasada llamada reducción a la mitad del camino: mientras recorremos la cadena hacia arriba, hacemos que cada nodo apunte a su abuelo en lugar de a su padre. Esto reduce a la mitad la longitud del camino en cada recorrido, sin una segunda pasada, y logra la misma complejidad amortizada O(alpha(n)) cuando se combina con union by rank.
La reducción a la mitad del camino suele preferirse en programación competitiva porque consiste en un único bucle claro, sin recursión ni un segundo recorrido. Cada paso ejecuta self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].
class DSUHalving:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # point to grandparent
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))Comprobar la conectividad después de las uniones
Para comprobar si dos nodos están conectados (en la misma componente), llame a find(x) == find(y). Si ambos devuelven la misma raíz, pertenecen a la misma componente. Esta es la consulta de conectividad y, con compresión de caminos, se ejecuta en un tiempo amortizado cercano a O(1).
En los problemas de entrevistas, las consultas de conectividad suelen aparecer intercaladas con operaciones union. El DSU gestiona ambas en línea: puede alternar uniones y consultas en cualquier orden. Esto distingue al DSU de algoritmos para grafos estáticos como BFS/DFS, que deben volver a ejecutarse después de cada cambio estructural.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
def connected(self, x, y):
return self.find(x) == self.find(y)
dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7)) # True: 0-3-7
print(dsu.connected(0, 5)) # False: different components
print(dsu.connected(1, 5)) # True: 1-5Errores comunes al implementar DSU
Un error frecuente consiste en llamar a find y modificar después parent de forma incorrecta. Llame siempre a find para ambos elementos antes de comprobar si son iguales; de lo contrario, podría comparar incorrectamente un nodo con su propia raíz. Otro error común es olvidar que union no debe hacer nada cuando ambos elementos ya comparten una raíz.
En Python, el límite de profundidad de recursión (1000 por defecto) puede provocar un RecursionError con cadenas grandes y un find recursivo. Puede usar la versión iterativa en dos pasadas, aumentar el límite con sys.setrecursionlimit o utilizar la reducción a la mitad del camino de forma iterativa para evitar por completo la recursión profunda.
import sys
sys.setrecursionlimit(10000) # needed for large recursive DSU
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
# Safe iterative path compression
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # already same component — do nothing
self.parent[px] = py
return True
dsu = DSU(5)
print(dsu.union(0, 1)) # True: merged
print(dsu.union(0, 1)) # False: already merged — no double-countingSeguimiento del tamaño en DSU
En algunos problemas necesita conocer el tamaño de cada componente, no solo su raíz. Añada un array size inicializado con todos sus valores a 1. Al fusionar dos componentes, sume el tamaño de la raíz menor al de la raíz mayor. Esto permite consultar en O(1) el tamaño de una componente después de cualquier union.
El seguimiento del tamaño también es la base de union by size (una alternativa a union by rank): siempre se adjunta el árbol más pequeño bajo la raíz del árbol más grande. Esto garantiza que la altura del árbol se mantenga en O(log n), con la misma garantía asintótica que union by rank.
class DSUWithSize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.size[px] < self.size[py]:
px, py = py, px # attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
def get_size(self, x):
return self.size[self.find(x)]
dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0)) # 3
print('Size of component containing 3:', dsu.get_size(3)) # 2
print('Size of component containing 5:', dsu.get_size(5)) # 1Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: DSU mantiene conjuntos disjuntos mediante las operaciones find y union, la compresión de caminos aplana el árbol haciendo que todos los nodos recorridos apunten directamente a la raíz y esto proporciona un rendimiento amortizado de find cercano a O(1). A continuación veremos union by rank, que mantiene los árboles poco profundos desde arriba para lograr la cota de la función de Ackermann inversa.
Preguntas frecuentes
¿La lección «DSU con compresión de caminos» es gratis?
Sí — el texto completo de «DSU con compresión de caminos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «DSU con compresión de caminos»?
Implemente find con compresión de caminos para que todos los nodos del camino apunten directamente a la raíz, logrando un coste amortizado de find cercano a O(1). Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «DSU con compresión de caminos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- DSU con compresión de caminos
- Unión por rango y cota de Ackermann inversa
- Conexión redundante y detección de ciclos
- Fusión de cuentas y componentes conexas