Implementación básica y aplicaciones de la estructura de datos Union-Find (Conjuntos Disjuntos).

Ejemplo Básico: Union-Find con Compresión de Rutas

Implementación estándar con las operaciones de find y union. Se utiliza compresión de rutas para optimizar las búsquedas.

#include <iostream>
using namespace std;

const int MAX_N = 10010;
int padre[MAX_N];

int buscar(int nodo) {
    if (nodo == padre[nodo])
        return nodo;
    return padre[nodo] = buscar(padre[nodo]);
}

void unir(int a, int b) {
    int raizA = buscar(a);
    int raizB = buscar(b);
    if (raizA != raizB)
        padre[raizA] = raizB;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++)
        padre[i] = i;
    
    for (int i = 0; i < m; i++) {
        int tipo, x, y;
        cin >> tipo >> x >> y;
        if (tipo == 1) {
            unir(x, y);
        } else {
            cout << (buscar(x) == buscar(y) ? "Y" : "N") << endl;
        }
    }
    
    return 0;
}

Relaciones de Amistad y Enemistad

Modelado de relaciones donde los amigos de amigos son amigos, y los enemigos de los enemigos son amigos. Se utiliza un arreglo adicional para rastrear enemigos directos.

#include <iostream>
using namespace std;

const int MAX_ACTORES = 1010;
int padre[MAX_ACTORES], enemigo_directo[MAX_ACTORES];

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

void fusionar(int u, int v) {
    int raizU = encontrar(u);
    int raizV = encontrar(v);
    if (raizU != raizV)
        padre[raizU] = raizV;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        padre[i] = i;
        enemigo_directo[i] = 0;
    }
    
    for (int i = 0; i < m; i++) {
        char relacion;
        int a, b;
        cin >> relacion >> a >> b;
        
        if (relacion == 'F') {
            fusionar(a, b);
        } else {
            if (enemigo_directo[a] == 0) {
                enemigo_directo[a] = encontrar(b);
            } else {
                fusionar(b, enemigo_directo[a]);
            }
            if (enemigo_directo[b] == 0) {
                enemigo_directo[b] = encontrar(a);
            } else {
                fusionar(a, enemigo_directo[b]);
            }
        }
    }
    
    int conteo_grupos[MAX_ACTORES] = {0};
    for (int i = 1; i <= n; i++)
        conteo_grupos[encontrar(i)]++;
    
    int grupos = 0;
    for (int i = 1; i <= n; i++)
        if (conteo_grupos[i] > 0) grupos++;
    
    cout << grupos << endl;
    return 0;
}

Cadena Alimentaria

Uso de union-find por rangos (tres dominios: mismo tipo, presa, depredador) para detectar contradicciones en afirmaciones sobre relaciones alimentarias.

#include <iostream>
using namespace std;

const int MAX_ANIMALES = 50010;
int padre[3 * MAX_ANIMALES]; // Índices: 1..n (mismo tipo), n+1..2n (presa), 2n+1..3n (depredador)

int buscar(int nodo) {
    if (padre[nodo] == nodo) return nodo;
    return padre[nodo] = buscar(padre[nodo]);
}

void fusionar(int a, int b) {
    int raizA = buscar(a);
    int raizB = buscar(b);
    if (raizA != raizB)
        padre[raizA] = raizB;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= 3 * n; i++)
        padre[i] = i;
    
    int falsas = 0;
    for (int i = 0; i < k; i++) {
        int tipo, x, y;
        cin >> tipo >> x >> y;
        
        if (x > n || y > n) {
            falsas++;
            continue;
        }
        
        if (tipo == 1) {
            if (buscar(x) == buscar(y + n) || buscar(x) == buscar(y + 2 * n)) {
                falsas++;
            } else {
                fusionar(x, y);
                fusionar(x + n, y + n);
                fusionar(x + 2 * n, y + 2 * n);
            }
        } else {
            if (x == y || buscar(x) == buscar(y) || buscar(x) == buscar(y + n)) {
                falsas++;
            } else {
                fusionar(x, y + 2 * n);
                fusionar(x + n, y);
                fusionar(x + 2 * n, y + n);
            }
        }
    }
    
    cout << falsas << endl;
    return 0;
}

Flota Galáctica

Implementación de union-find con pesos (distancias relativas) para calcular distancias entre naves en una misma formación.

#include <iostream>
#include <cmath>
using namespace std;

const int MAX_NAVES = 30010;
int padre[MAX_NAVES], distancia[MAX_NAVES], tamanio[MAX_NAVES];

int buscar(int nave) {
    if (padre[nave] == nave) return nave;
    int raiz = buscar(padre[nave]);
    distancia[nave] += distancia[padre[nave]];
    return padre[nave] = raiz;
}

void mover(int origen, int destino) {
    int raizO = buscar(origen);
    int raizD = buscar(destino);
    padre[raizO] = raizD;
    distancia[raizO] = tamanio[raizD];
    tamanio[raizD] += tamanio[raizO];
}

int main() {
    int T;
    cin >> T;
    
    for (int i = 1; i < MAX_NAVES; i++) {
        padre[i] = i;
        distancia[i] = 0;
        tamanio[i] = 1;
    }
    
    while (T--) {
        char comando;
        int i, j;
        cin >> comando >> i >> j;
        
        if (comando == 'M') {
            mover(i, j);
        } else {
            if (buscar(i) != buscar(j)) {
                cout << -1 << endl;
            } else {
                cout << abs(distancia[i] - distancia[j]) - 1 << endl;
            }
        }
    }
    
    return 0;
}

Mantenimiento de Conectividad en Secuencias

Uso de union-find para procesar operaciones de coloreado por intervalos en orden inverso, manteniendo un puntero al siguiente elemento disopnible.

#include <iostream>
using namespace std;

const int MAX_COPOS = 1000010;
int padre[MAX_COPOS], color[MAX_COPOS];

int siguiente(int pos) {
    if (padre[pos] == pos) return pos;
    return padre[pos] = siguiente(padre[pos]);
}

int main() {
    int n, m, p, q;
    cin >> n >> m >> p >> q;
    
    for (int i = 1; i <= n; i++)
        padre[i] = i;
    
    for (int i = m; i >= 1; i--) {
        int izquierda = (i * p + q) % n + 1;
        int derecha = (i * q + p) % n + 1;
        if (izquierda > derecha) swap(izquierda, derecha);
        
        int pos = derecha;
        while (pos >= izquierda) {
            int pos_actual = siguiente(pos);
            if (pos_actual < izquierda) break;
            color[pos_actual] = i;
            padre[pos_actual] = siguiente(pos_actual - 1);
            pos = pos_actual - 1;
        }
    }
    
    for (int i = 1; i <= n; i++)
        cout << color[i] << endl;
    
    return 0;
}

Verificación de Camino Euleriano

Uso de union-find para verificar la conectividad del grafo en problemas de cadenas de colores, complementando el conteo de grados impares para determinar la existencia de un camino euleriano.

#include <iostream>
#include <string>
#include <map>
using namespace std;

const int MAX_ELEMENTOS = 500010;
int padre[MAX_ELEMENTOS], grado[MAX_ELEMENTOS];

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

void fusionar(int a, int b) {
    int raizA = buscar(a);
    int raizB = buscar(b);
    if (raizA != raizB)
        padre[raizA] = raizB;
}

int main() {
    map<string, int> mapeo_colores;
    int total_elementos = 0;
    int total_aristas = 0;
    
    string color1, color2;
    while (cin >> color1 >> color2) {
        total_aristas++;
        
        if (mapeo_colores.find(color1) == mapeo_colores.end())
            mapeo_colores[color1] = ++total_elementos;
        if (mapeo_colores.find(color2) == mapeo_colores.end())
            mapeo_colores[color2] = ++total_elementos;
        
        int id1 = mapeo_colores[color1];
        int id2 = mapeo_colores[color2];
        
        grado[id1]++;
        grado[id2]++;
        fusionar(id1, id2);
    }
    
    int raiz_principal = buscar(1);
    for (int i = 2; i <= total_elementos; i++) {
        if (buscar(i) != raiz_principal) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    
    int vertices_grado_impar = 0;
    for (int i = 1; i <= total_elementos; i++) {
        if (grado[i] % 2 != 0)
            vertices_grado_impar++;
    }
    
    if (vertices_grado_impar == 0 || vertices_grado_impar == 2)
        cout << "Possible" << endl;
    else
        cout << "Impossible" << endl;
    
    return 0;
}

Consideraciones de Implementación

• Siempre fusionar las raíces de los conjuntos, no los nodos directamente.
• En union-find con pesos, la dirección de la fusión determina el signo del peso.
• La compresión de rutas es esencial para mantener la eficiencia.
• Para problemas de coloreado o actualización por intervalos, considerar el procesamiento en orden inverso.