Conectividad Dinámica

En este manual veremos una modificación de la Estructura Unión-Búsqueda de componentes de un grafo, de forma que, además de procesar las dos peticiones

• Añadir una arista al grafo
• ¿A qué componente pertenece un nodo?
• ¿Cuántas componentes hay en total?

También podremos hacer un tipo de petición extra:

• Eliminar una arista existente del grafo

Idea de la estructura

Para hacerlo, vamos a procesar las peticiones de forma offline, es decir, que primero vamos a leer todas las peticiones y con esta información nos haremos una estructura de datos que nos permitirá responderlas más fácilmente.

En concreto, cuando leamos todas las peticiones nos guardaremos en que intervalos de tiempo (decimos que por cada petición del segundo o tercer tipo pasa un instante de tiempo) existe cada arista y con estos intervalos nos haremos un árbol de segmentos en el que las hojas serán los instantes de tiempo y para cada nodo nos guardaremos las aristas que existan en todo su intervalo (pero que no estén ya en el padre de esta). Y después podremos recorrer el árbol en pre-orden, de forma que cuando entramos a un nodo añadimos todas las aristas de ese nodo y cuando salimos de él deshacemos todos los cambios que habíamos hecho, y cuando lleguemos a una hoja contestaremos a la pregunta que le corresponda.

Implementación

La implementación del árbol de segmentos (con structs) quedaría de la siguiente forma:

#define edge pair<int, int>
#define x first
#define y second
vector<int> dsu;
vector<int> sizes;
int components;
int findSet(int x) {
    return dsu[x] == x ? x : findSet(dsu[x]);
}

struct node {
    int a, b;
    node *l, *r;
    vector<edge> additions; // aristas que existiran en este nodo

    node(int x, int y) {
        a = x; b = y;
        if(x == y-1)
            l = r = nullptr;
        else {
            l = new node(x, (x+y)/2);
            r = new node((x+y)/2, y);
        }
    }

    void insert(int x, int y, edge e) {
        if(y <= a or x >= b)
            return;
        if(x <= a and y >= b)
            additions.push_back(e);
        else {
            l->insert(x, y, e);
            r->insert(x, y, e);
        }
    }

    void run() {
        // Nos guardaremos los cambios que hagamos para deshacerlos
        vector<int> changes; // los vertices que eran representantes de su componente y dejan de serlo
        map<int, int> change2; // los vertices cuyo tamaño cambia y cuanto era antes
        
        // empezamos añadiendo todas las aristas
        for(edge e: additions) {
            int pap1 = findSet(e.x), pap2 = findSet(e.y);
            if(sizes[pap1] < sizes[pap2])
                swap(pap1, pap2);
            if(pap1 != pap2) {
                // guardamos los cambios antes de realizarlos
                changes.push_back(pap2);
                if(change2.find(pap1) == change2.end())
                    change2[pap1] = sizes[pap1];
                // y los hacemos
                dsu[pap2] = pap1;
                sizes[pap1] = sizes[pap1]+sizes[pap2];
            }
        }

        components -= changes.size();


        if(a != b-1) {
            // recurrimos a los dos hijos
            l->run();
            r->run();
        } else {
            // o respondemos la query si somos una hoja
            cout << components << '\n';
        }

        // deshacemos los cambios
        for(int x: changes)
            dsu[x] = x;
        for(auto [x, d]: change2)
            sizes[x] = d;
        components += changes.size();
    }
};

Esta implementación solo responde a peticiones del tipo 3, no del tipo 2. Añadir el segundo tipo de peticiones no es muy complicado y se deja como ejercicio para el lector.

Ahora solo faltaría inicializarlo con los valores oportunos y llamar a la función run.

Complejidad

Como mucho tendremos $q/2$ intervalos donde existe una arista concreta, donde $q$ es el número de peticiones que nos hacen. Y cada intervalo nos cuesta $\log(q)$ procesarlo, la complejidad del árbol de segmentos. Por tanto, crearlo nos costará $\mathcal O (q\log(q))$. Y después volver a pasar por todo el árbol también nos costará $\mathcal O (q\log(q))$, porque aunque pasamos por $\mathcal O (q)$ nodos, en cada uno de ellos tendremos que hacer varias operaciones, una por cada arista de ese nodo y, como nos cuesta $\mathcal O (q\log(q))$ crear el árbol, como mucho en total tendremos $\mathcal O (q\log(q))$ aristas entre todos los nodos. Y para cada arista tenemos que llamar a la función $findSet$, que tiene coste $\mathcal O (\log(n))$ en el peor caso, donde $n$ es el número de vértices del grafo. Hace falta remarcar que es importante hacer la optimización del tamaño de la Estructura Unión-Busqueda, para que este coste sea $\mathcal O (\log(n))$ en lugar de $\mathcal O (n)$, pero no se puede hacer la optimización de compresión de caminos, porque después no podríamos deshacer los cambios.

Por tanto, la complejidad total del algoritmo entero es $\mathcal O (q\log(q)\log(n))$.