Union-Find (DSU)

¿Qué es Union-Find?

Analogía: Imagina un grupo de personas. Al principio, cada persona está sola. Cuando dos personas se hacen amigas, sus grupos se fusionan (si Ana es amiga de Luis, y Luis de Pedro, entonces Ana y Pedro están en el mismo grupo). Union-Find maneja esto eficientemente.

Soporta dos operaciones:

• Find(x): ¿A qué grupo pertenece x?
• Union(a, b): Fusionar los grupos de a y b.

Implementación con optimizaciones

const int MAXN = 100005;
int padre[MAXN], rango[MAXN], tam[MAXN];

void inicializar(int n) {
    for (int i = 1; i <= n; i++) {
        padre[i] = i;
        rango[i] = 0;
        tam[i] = 1;
    }
}

// Find con compresión de caminos
int encontrar(int x) {
    if (padre[x] != x) {
        padre[x] = encontrar(padre[x]);
    }
    return padre[x];
}

// Union por rango
bool unir(int a, int b) {
    a = encontrar(a);
    b = encontrar(b);
    if (a == b) return false;

    if (rango[a] < rango[b]) swap(a, b);
    padre[b] = a;
    tam[a] += tam[b];
    if (rango[a] == rango[b]) rango[a]++;

    return true;
}

bool conectados(int a, int b) {
    return encontrar(a) == encontrar(b);
}

int tamComponente(int x) {
    return tam[encontrar(x)];
}

Compresión de caminos

Sin optimización, encontrar puede ser $O(n)$. Con compresión, cada nodo apunta directamente a la raíz:

Antes:  1 → 2 → 3 → 4 (raíz)
Después: 1 → 4, 2 → 4, 3 → 4

Unión por rango

Siempre colgar el árbol más bajo del más alto, para mantener la altura mínima.

Complejidad amortizada: $O(\alpha(n))$ ≈ $O(1)$ por operación.

Aplicaciones

Contar componentes después de agregar aristas

int main() {
    int n, m;
    cin >> n >> m;
    inicializar(n);

    int componentes = n;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if (unir(u, v)) {
            componentes--;
        }
        cout << "Componentes: " << componentes << endl;
    }
}

Detectar ciclos al agregar aristas

for (auto [u, v] : aristas) {
    if (!unir(u, v)) {
        cout << "Arista (" << u << "," << v << ") forma un ciclo" << endl;
    }
}

Kruskal (MST)

Union-Find es fundamental para el algoritmo de Kruskal (ver sección de MST).

Ejercicio de práctica

N personas y Q operaciones. Operación 1: "A y B son amigos". Operación 2: "¿A y B son amigos (directa o indirectamente)?".

#include <iostream>
using namespace std;

int padre[100005], rk[100005];

int encontrar(int x) {
    if (padre[x] != x) padre[x] = encontrar(padre[x]);
    return padre[x];
}

void unir(int a, int b) {
    a = encontrar(a); b = encontrar(b);
    if (a == b) return;
    if (rk[a] < rk[b]) swap(a, b);
    padre[b] = a;
    if (rk[a] == rk[b]) rk[a]++;
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) { padre[i] = i; rk[i] = 0; }

    while (q--) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) unir(a, b);
        else cout << (encontrar(a) == encontrar(b) ? "SI" : "NO") << endl;
    }
    return 0;
}