DSU con compresión de caminos
Encuentre y una conjuntos en tiempo casi constante
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é registra DSU
Una Disjoint Set Union mantiene los elementos agrupados en conjuntos que no se solapan, de modo que puede comprobar si dos elementos ya pertenecen al mismo grupo. 🤝
Los conjuntos como árboles
DSU almacena cada conjunto como un árbol. Cada elemento apunta a un padre y el nodo situado más arriba, la raíz, es el nombre único de todo el grupo.
El arreglo de padres
Guarde todos esos enlaces en un único arreglo. Comience con cada elemento como su propio padre, lo que significa que cada elemento empieza en un conjunto independiente.
parent = list(range(n))Encuentre la raíz
La operación find recorre los enlaces de padres hasta que un elemento apunta a sí mismo. Ese nodo que se apunta a sí mismo es la raíz que identifica el conjunto.
while parent[x] != x:
x = parent[x]Las cadenas largas perjudican
Sin cuidado, los conjuntos pueden formar cadenas largas y estrechas. Entonces find avanza nodo por nodo y una sola consulta puede costar O(n), lo cual es demasiado lento.
Aparece la compresión de caminos
La compresión de caminos lo soluciona: mientras encuentra la raíz, vuelve a apuntar directamente a ella cada nodo visitado, aplanando el árbol para la próxima vez. ⚡
Compresión recursiva
La forma más limpia es utilizar recursión. Encuentre la raíz y después guárdela de nuevo en parent[x] antes de devolver el resultado, para acortar permanentemente el enlace.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]¿Dos elementos del mismo conjunto?
Para comprobar si dos elementos están conectados, compare sus raíces. Si find(a) equals find(b), pertenecen al mismo grupo; de lo contrario, siguen separados.
if find(a) == find(b):
print("connected")Una dos conjuntos
La operación union une los grupos haciendo que una raíz apunte a la otra. Una sola línea enlaza dos árboles completos en un único conjunto.
def union(a, b):
parent[find(a)] = find(b)Por qué es tan rápido
Solo con la compresión, las operaciones se ejecutan aproximadamente en O(log n) amortizado; combinada con el uso de rangos, alcanzan un tiempo casi constante por consulta.
Dónde destaca DSU
DSU permite resolver problemas de conectividad: los círculos de amigos, los componentes de una red y el árbol de expansión de Kruskal dependen de operaciones rápidas de find y union. 🌐
Comprobación rápida
Considere qué cambia realmente la compresión de caminos.
Repaso
Ha creado un DSU: un arreglo de padres, find para obtener la raíz y union para fusionar conjuntos. La compresión de caminos lo mantiene rapidísimo. ¡Buen trabajo! 🎉
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»?
Encuentre y una conjuntos en tiempo casi constante 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 componentes
- Árbol de expansión mínima de Kruskal
- MST de Prim con un heap