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ón | Grupos 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.
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).
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ón | find de cada lado | qué pasa | grupos después |
|---|---|---|---|
unir(1, 2) | 1, 2 | jefes distintos, tamaños iguales: 2 bajo 1 | {1,2} {3} {4} {5} {6} |
unir(3, 4) | 3, 4 | 4 bajo 3 | {1,2} {3,4} {5} {6} |
unir(2, 4) | 1, 3 | tamaños 2 y 2: 3 bajo 1 | {1,2,3,4} {5} {6} |
unir(5, 6) | 5, 6 | 6 bajo 5 | {1,2,3,4} {5,6} |
unir(1, 3) | 1, 1 | mismo jefe: devuelve false (cerraría un ciclo) | sin cambios |
unir(6, 4) | 5, 1 | tamañ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.
Idea para comprobar tu solución
Reduce el contador solo si unir devuelve true. La tercera carretera agrega una arista, pero no fusiona grupos.
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?
Una pista, si la necesitas
Una orden puede conectar vértices que ya estaban en el mismo grupo.
Contrastar el razonamiento
Quedan dos. Solo disminuye el contador cuando las raíces eran distintas: la tercera unión no fusiona componentes nuevos.
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.
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Road Construction (CSES 1676) | ★★★ (—) | la definición: grupos y tamaño máximo en vivo |
| 2 | Rumor (893C) | ★★★ (1300) | mínimo por grupo |
| 3 | ⭐ News Distribution (1167C) | ★★★ (1400) | tamaños de grupo por consulta |
Desafío OCI (en español)
| Problema | Fase | Qué practica |
|---|---|---|
| ⭐⭐ Ca-chi-pún | Clasificatoria 2017 | DSU 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?
Ver razonamiento
Conectados significa que existe un camino: aquí es
A–B–C. Los padres de DSU representan grupos; no tienen por qué ser aristas del grafo original. El DSU básico fusiona grupos al insertar aristas, pero no sabe dividirlos cuando una arista desaparece. Tras eliminarB–Cseguiría diciendo que A y C están juntos. Para consultar el grafo resultante en este caso pequeño, se pueden recalcular sus componentes con DFS o BFS.
← 18 - Grafos II - Dijkstra y DAGs · Ruta de Aprendizaje · 20 - Fenwick y segment tree →