19 · Union-Find (DSU)

Estructuras y algoritmos avanzados · Ruta de Aprendizaje

Esta clase explica cómo mantener grupos conectados. La ficha DSU (Union-Find) desarrolla la implementación completa y sus detalles.

Antes de empezar. Representar componentes de un grafo: 15 - Grafos I - BFS y DFS; funciones recursivas: 09 - Recursión.

🎯 Objetivos

Al terminar este módulo sabes:

  • Mantener grupos que se fusionan con costo casi constante.
  • Responder “¿están en el mismo grupo?” y “¿de qué tamaño es?” al vuelo.
  • Distinguir cuándo DSU le gana al DFS del módulo 15.

📖 La lección

El problema que resuelve

Con DFS cuentas componentes de un grafo fijo. Pero si las conexiones van apareciendo (se construye una carretera, dos personas se hacen amigas) y entre medio te preguntan por los grupos, rehacer el DFS para q consultas puede costar O(q·(n+m)), con n nodos y hasta m aristas. El Disjoint Set Union mantiene los grupos al día en tiempo casi constante por operación.

Antes del árbol: qué debe recordar

Partimos de cuatro personas separadas: {1}, {2}, {3}, {4}.

OperaciónGrupos después¿1 y 3 están conectadas?
unir 1 y 2{1,2}, {3}, {4}no
unir 2 y 3{1,2,3}, {4}sí, a través de 2
unir 1 y 3{1,2,3}, {4}sí; no cambia el grupo

No necesitamos guardar el camino para responder pertenencia. Sí debemos recordar que 1, 2 y 3 forman un mismo grupo y que tiene tamaño tres. El bosque interno que construiremos representa esos grupos: sus flechas no tienen por qué ser conexiones del grafo original. El DSU básico fusiona grupos; no sabe separarlos al borrar una carretera.

Cómo funciona

Cada grupo tiene un jefe (representante). Cada elemento apunta hacia su jefe a través de una cadena; dos elementos están en el mismo grupo si tienen el mismo jefe.

antes: dos grupos, dos jefes12345tam[1] = 3tam[4] = 2unir(3, 5): find(3) = 1, find(5) = 4jefes distintos → se juntan; el chico bajo el grandedespués: un solo grupo12345tam[1] = 5; find(5) sube 5 → 4 → 1

Si el diagrama no cabe, deslízalo horizontalmente.

Primero imagina una versión sin optimizaciones: cada persona apunta a un padre; una raíz apunta a sí misma. Para consultar un grupo seguimos padres hasta la raíz. Para unir dos grupos enlazamos una raíz con la otra; si ya coinciden, no cambiamos nada.

Por ejemplo, en 4→3→1, el representante de 4 es 1. Podemos acortar futuras consultas haciendo que 4 apunte directamente a 1: es compresión de camino. Además, enlazamos la raíz del grupo pequeño bajo la del grande, para no alargar innecesariamente las cadenas. tam solo es fiable en las raíces. Ahora implementamos esas dos mejoras sobre las operaciones anteriores:

vector<int> jefe, tam;          // globales
 
void iniciar(int n) {           // cada elemento parte solo, jefe de sí mismo
    jefe.resize(n + 1);
    tam.assign(n + 1, 1);
    for (int i = 0; i <= n; i++) jefe[i] = i;
}
 
int find(int x) {
    if (jefe[x] == x) return x;
    return jefe[x] = find(jefe[x]); // compresión de camino
}
 
bool unir(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return false;      // ya estaban juntos
    if (tam[a] < tam[b]) swap(a, b);
    jefe[b] = a;                   // el grupo chico se cuelga del grande
    tam[a] += tam[b];
    return true;
}

Los dos trucos — compresión de camino (al buscar, re-apunta todo directo al jefe) y unión por tamaño (el chico se cuelga del grande) — dejan cada operación con costo amortizado O(α(n)), prácticamente constante. «Amortizado» describe el costo promedio sobre una secuencia de operaciones, no que cada llamada haga exactamente el mismo trabajo. El tamaño del grupo de x es tam[find(x)]: solo el representante mantiene el tamaño actualizado. Referencia completa: DSU (Union-Find).

antes de find(5): una cadena12345find(5) sube 4 pasos…y de paso re-apunta tododespués: una estrella12345el próximo find de cualquiera de ellos es 1 pasounión por tamaño evita que se formen cadenas largas; la compresión las deshace si aparecen

Si el diagrama no cabe, deslízalo horizontalmente.

Antes de unir o consultar, llama iniciar(n). En la tabla usamos nodos 1..n y dejamos el 0 sin usar. Por ejemplo, después de iniciar(6) y unir(1, 2), find(1) == find(2) es verdadero y tam[find(2)] vale 2.

Sigue una secuencia completa (parten 6 elementos, cada uno jefe de sí mismo):

operaciónfind de cada ladoqué pasagrupos después
unir(1, 2)1, 2jefes distintos, tamaños iguales: 2 bajo 1{1,2} {3} {4} {5} {6}
unir(3, 4)3, 44 bajo 3{1,2} {3,4} {5} {6}
unir(2, 4)1, 3tamaños 2 y 2: 3 bajo 1{1,2,3,4} {5} {6}
unir(5, 6)5, 66 bajo 5{1,2,3,4} {5,6}
unir(1, 3)1, 1mismo jefe: devuelve false (cerraría un ciclo)sin cambios
unir(6, 4)5, 1tamaños 2 y 4: 5 bajo 1{1,2,3,4,5,6}

Ese false de la quinta fila detecta ciclos al insertar aristas en un grafo no dirigido: una arista que une dos nodos que ya estaban en el mismo grupo cierra un ciclo. Es el corazón de Kruskal (MST).

En la cadena 4→3→1, find(4) llama a find(3), que llega a la raíz 1. Al volver, guarda jefe[3]=1 y luego jefe[4]=1. Las pertenencias no cambian: solo se acorta el recorrido de futuras consultas. No necesitas calcular α(n) para usar la estructura; sí conservar ambas optimizaciones.

Para contar componentes desde main, después de definir las funciones:

// usa: iniciar, find, unir
iniciar(4);
int componentes = 4;
for (auto [a, b] : vector<pair<int,int>>{{1,2},{2,3},{1,3},{3,4}}) {
    if (unir(a,b)) componentes--;
    cout << componentes << "\n"; // 3, 2, 2, 1
}

La conexión 1–3 no reduce el contador porque esos nodos ya estaban juntos. DSU no detecta con este criterio los ciclos dirigidos: para ellos usamos, por ejemplo, Kahn.

Dónde brilla

Conectividad incremental (“después de cada carretera, ¿cuántas provincias?”), detectar si una arista cierra ciclo, y — más adelante — es el corazón de Kruskal (MST). Si el grafo es fijo y la pregunta es una sola, el DFS sigue siendo suficiente; DSU gana cuando el grafo evoluciona.

🏋️ Práctica

Práctica directa: Carreteras que unen grupos

Empieza con 4 nodos. Inserta 1–2,2–3,1–3,3–4; después de cada arista imprime el número de componentes. Salida: 3 2 2 1.

Variación: Repetir una unión

Partes con cinco vértices separados. Ejecuta unir(0,1), unir(1,2), unir(0,2), unir(3,4). ¿Cuántos componentes quedan?

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

#ProblemaDificultadQué practica
1Road Construction (CSES 1676)★★★ (—)la definición: grupos y tamaño máximo en vivo
2Rumor (893C)★★★ (1300)mínimo por grupo
3⭐ News Distribution (1167C)★★★ (1400)tamaños de grupo por consulta

Desafío OCI (en español)

ProblemaFaseQué practica
⭐⭐ Ca-chi-púnClasificatoria 2017DSU con potenciales módulo 3 — nivel selección IOI

Para pensar: el bosque de DSU no es el grafo

Insertas las aristas A–B y B–C. DSU informa que A y C están conectados. ¿Significa que existe una arista A–C? Si ahora eliminas B–C, ¿basta con consultar de nuevo el mismo DSU?


← 18 - Grafos II - Dijkstra y DAGs · Ruta de Aprendizaje · 20 - Fenwick y segment tree →