CAPC-ITM

DSU en C++

La técnica de DSU se puede implementar en C++ utilizando una estructura de datos eficiente llamada "Union-Find". Aquí tienes una implementación básica:

#include <bits/stdc++.h>
using namespace std;

class DSU {
private:
    vector<int> parent;
    vector<int> rank;

public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 1); // Inicialmente, cada elemento es su propio conjunto de tamaño 1
        for (int i = 0; i < n; ++i)
            parent[i] = i; // Cada elemento es su propio representante al inicio
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // Path compression
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY])
                swap(rootX, rootY);
            parent[rootX] = rootY;
            if (rank[rootX] == rank[rootY])
                rank[rootY]++;
        }
    }
};

Aquí hay un ejemplo de cómo usar esta implementación de DSU:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5; // Número de elementos
    DSU dsu(n);

    // Unir algunos conjuntos
    dsu.unite(0, 1);
    dsu.unite(2, 3);
    dsu.unite(0, 4);

    // Encontrar representantes de algunos elementos
    cout << "Representante de 1: " << dsu.find(1) << endl;
    cout << "Representante de 3: " << dsu.find(3) << endl;

    return 0;
}

¿Qué es DSU?

DSU (Disjoint Set Union) o Union-Find es una estructura de datos que mantiene una colección de conjuntos disjuntos (que no se superponen). Permite realizar dos operaciones principales de manera eficiente:

• Find: Determinar a qué conjunto pertenece un elemento específico
• Union: Unir dos conjuntos en uno solo

Aplicaciones de DSU

DSU es especialmente útil en problemas que involucran:

• Detección de ciclos en grafos
• Algoritmo de Kruskal para encontrar el árbol de expansión mínima
• Problemas de conectividad en redes
• Agrupación dinámica de elementos

Optimizaciones

La implementación mostrada incluye dos optimizaciones importantes:

• Path Compression: En la función find, hacemos que todos los nodos en el camino apunten directamente a la raíz
• Union by Rank: Siempre unimos el árbol más pequeño al más grande para mantener la altura mínima

Estas optimizaciones hacen que las operaciones sean prácticamente constantes en tiempo amortizado.