Unión por rango y componentes
Mantenga los árboles planos y cuente grupos
Unión por rango y componentes es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 2 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 Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
union puede ser poco cuidadosa
La operación union básica simplemente cuelga una raíz debajo de otra. Si se hace sin cuidado, puede crear un árbol alto y lento, así que necesitamos una forma más inteligente de fusionar las raíces.
La idea principal
La unión por rango siempre coloca el árbol más corto debajo del más alto. Mantener los árboles bajos hace que cada find posterior sea más rápido. 📏
Qué significa el rango
El rango es una estimación de la altura de un árbol. Cada elemento empieza con rango 0, ya que un nodo individual no tiene profundidad por debajo.
rank = [0] * nUna el árbol más corto al más alto
Compare los rangos de las dos raíces. La raíz con el rango menor se convierte en hija, para que el árbol combinado permanezca lo más plano posible.
if rank[ra] < rank[rb]:
parent[ra] = rbLos empates aumentan el rango
Cuando ambas raíces tienen el mismo rango, elija cualquiera como nueva raíz y aumente su rango en uno, ya que el árbol acaba de crecer un nivel.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1Variante: unión por tamaño
Una alternativa popular es la unión por tamaño: coloque el conjunto más pequeño debajo del más grande. Es igual de eficaz y proporciona el tamaño de los grupos sin costo adicional.
Cuente los componentes
Comience un contador en n, ya que cada elemento es su propio grupo. Cada unión exitosa combina dos grupos en uno, así que debe disminuirlo.
components = nOmita las uniones sin efecto
Si dos elementos ya comparten una raíz, union no hace nada. Disminuya el contador solo cuando sus raíces sean diferentes.
if find(a) != find(b):
union(a, b)
components -= 1Rango más compresión
Combine la unión por rango con la compresión de caminos y DSU se ejecutará en tiempo inverso de Ackermann, que es efectivamente constante para cualquier entrada real. ⚡
Tamaños de grupo bajo demanda
Con la unión por tamaño puede responder al instante cuál es el tamaño de cualquier grupo: basta con leer el tamaño almacenado en la raíz del elemento.
group = size[find(x)]Dónde resulta útil
Contar componentes responde preguntas clásicas, como cuántos círculos de amistades o regiones conexas quedan después de una secuencia de llamadas a union. 🌐
Comprobación rápida
Razone sobre cómo cambia el contador de componentes.
Repaso
Aprendió unión por rango para mantener los árboles planos y a llevar un registro del número de componentes y del tamaño de los grupos. ¡DSU ahora es rapidísimo! 🎉
Preguntas frecuentes
¿La lección «Unión por rango y componentes» es gratis?
Sí — el texto completo de «Unión por rango y componentes» 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 Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Unión por rango y componentes»?
Mantenga los árboles planos y cuente grupos Practicas Competitive Programming Academy 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 Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy 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 2 de 4.
¿Cuánto tiempo toma la lección «Unión por rango y componentes»?
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 Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy 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