Conectividad Dinámica | Conjunto 2 (DSU con reversión)

La conectividad dinámica, en general, se refiere al almacenamiento de la conectividad de los componentes de un gráfico, donde los bordes cambian entre algunas o todas las consultas. Las operaciones básicas son: 

1. Agregue un borde entre los Nodes a y b
2. Eliminar el borde entre los Nodes a y b

Tipos de problemas al usar la Conectividad Dinámica

Los problemas que utilizan la conectividad dinámica pueden ser de las siguientes formas: 

• Edges agregados solamente (puede llamarse «Conectividad incremental») : use una estructura de datos DSU.
• Solo bordes eliminados (puede ser «Conectividad decreciente») : comience con el gráfico en su estado final después de eliminar todos los bordes requeridos. Procese las consultas desde la última consulta hasta la primera (en el orden inverso). Agregue los bordes en el orden opuesto al que se quitaron. 
• Bordes agregados y eliminados (puede llamarse «Conectividad totalmente dinámica») : esto requiere una función de reversión para la estructura de la DSU, que puede deshacer los cambios realizados en una DSU, devolviéndola a un punto determinado en su historial. Esto se denomina DSU con reversión.

DSU con reversión

La DSU con reversión se realiza siguiendo los pasos a continuación donde el historial de una DSU se puede almacenar usando pilas . 

• En la siguiente implementación, usamos 2 pilas : 
  • Una de las pilas (Pila 1) almacena un puntero a la posición en la array (array de rango o array principal) que hemos cambiado, y 
  • En el otro (Pila 2) almacenamos el valor original almacenado en esa posición (alternativamente, podemos usar una sola pila de una estructura como pares en C++).
• Para deshacer el último cambio realizado en la DSU, establezca el valor en la ubicación indicada por el puntero en la parte superior de la Pila 1 en el valor en la parte superior de la Pila 2 . Pop un elemento de ambas pilas. 
• Cada punto en el historial de modificación del gráfico está determinado únicamente por la longitud de la pila una vez que se realiza la modificación final para llegar a ese estado. 
• Entonces, si queremos deshacer algunos cambios para alcanzar cierto estado, todo lo que necesitamos saber es la longitud de la pila en ese punto. Luego, podemos sacar elementos de la pila y deshacer esos cambios, hasta que la pila tenga la longitud requerida.

El código para la implementación genérica es el siguiente:

#include <iostream>
using namespace std;
  
const int MAX_N = 1000;
int sz = 0, v[MAX_N], p[MAX_N], r[MAX_N];
int* t[MAX_N];
  
void update(int* a, int b)
{
    if (*a != b) {
        t[sz] = a;
        v[sz] = *a;
        *a = b;
        sz++;
    }
}
  
void rollback(int x)
{
    // Undo the changes made,
    // until the stack has length sz
    for (; sz > x;) {
        sz--;
        *t[sz] = v[sz];
    }
}
  
int find(int n)
{
    return p[n] ? find(p[n]) : n;
}
  
void merge(int a, int b)
{
    // Parent elements of a and b
    a = find(a), b = find(b);
    if (a == b)
        return;
  
    // Merge small to big
    if (r[b] > r[a])
        std::swap(a, b);
  
    // Update the rank
    update(r + a, r[a] + r[b]);
  
    // Update the parent element
    update(p + b, a);
}
  
int main()
{
    return 0;
}

Ejemplo para entender la conectividad dinámica

Veamos un ejemplo para una mejor comprensión del concepto. 

Dado un gráfico con N Nodes (etiquetados de 1 a N) y sin bordes inicialmente, y Q consultas. Cada consulta agrega o elimina un borde del gráfico. Nuestra tarea es informar el número de componentes conectados después de que se procese cada consulta (Q líneas de salida). Cada consulta es de la forma {i, a, b} donde 

• si i = 1 entonces se suma una arista entre a y b
• Si i = 2, entonces se elimina un borde entre a y b

Ejemplos

Entrada:  N = 3, Q = 4, consultas = { {1, 1, 2}, {1, 2, 3}, {2, 1, 2}, {2, 2, 3} }
Salida:  2 1 2 3
Explicación: 

La imagen muestra cómo cambia el gráfico en cada una de las 4 consultas y cuántos componentes conectados hay en el gráfico.

Entrada:  N = 5, Q = 7, consultas = { {1, 1, 2}, {1, 3, 4}, {1, 2, 3}, {1, 1, 4}, {2, 2, 1}, {1, 4, 5}, {2, 3, 4} }
Salida:  4 3 2 2 2 1 2
Explicación: 

La imagen muestra cómo cambia el gráfico en cada una de las 7 consultas y cuántos componentes conectados hay en el gráfico.

Enfoque: el problema se puede resolver con una combinación de DSU con rollback y divide y vencerás basado en la siguiente idea:

Las consultas se pueden resolver sin conexión. Piense en las consultas Q como una línea de tiempo. 

• Para cada borde, que en algún momento formó parte del gráfico, almacene los intervalos disjuntos en la línea de tiempo donde existe este borde en el gráfico.
• Mantenga una DSU con reversión para agregar y eliminar bordes del gráfico. 

El enfoque divide y vencerás se utilizará en la línea de tiempo de las consultas. Se llamará a la función para los intervalos (l, r) en la línea de tiempo de las consultas. esa voluntad: 

• Agregue todos los bordes que están presentes en el gráfico para todo el intervalo (l, r) .
• Llame recursivamente a la misma función para los intervalos (l, mid) y (mid+1, r) [si el intervalo (l, r) tiene una longitud de 1 , responda la l ^-ésima consulta y guárdela en una array de respuestas). 
• Llame a la función de reversión para restaurar el gráfico a su estado en la llamada de función. 

A continuación se muestra la implementación del enfoque anterior: 

// C++ code to implement the approach
  
#include <bits/stdc++.h>
using namespace std;
  
int N, Q, ans[10];
  
// Components and size of the stack
int nc, sz;
map<pair<int, int>, vector<pair<int, int> > > graph;
  
// Parent and rank array
int p[10], r[10];
int *t[20], v[20];
  
// Stack3 - stores change in number of components
// component) only changes for updates to p, not r
int n[20];
  
// Function to set the stacks
// for performing DSU rollback
int setv(int* a, int b, int toAdd)
{
    t[sz] = a;
    v[sz] = *a;
    *a = b;
    n[sz] = toAdd;
    ++sz;
    return b;
}
  
// Function fro performing rollback
void rollback(int x)
{
    for (; sz > x;) {
        --sz;
        *t[sz] = v[sz];
        nc += n[sz];
    }
}
  
// Function to find the parents
int find(int n)
{
    return p[n] ? find(p[n]) : n;
}
  
// Function to merge two disjoint sets
bool merge(int a, int b)
{
    a = find(a), b = find(b);
    if (a == b)
        return 0;
    nc--;
    if (r[b] > r[a])
        std::swap(a, b);
    setv(r + b, r[a] + r[b], 0);
    return setv(p + b, a, 1), 1;
}
  
// Function to find the number of connected components
void solve(int start, int end)
{
    // Initial state of the graph,
    // at function call determined by
    // the length of the stack at this point
    int tmp = sz;
  
    // Iterate through the graph
    for (auto it = graph.begin();
         it != graph.end(); ++it) {
  
        // End nodes of edge
        int u = it->first.first;
        int v = it->first.second;
  
        // Check all intervals where its present
        for (auto it2 = it->second.begin();
             it2 != it->second.end(); ++it2) {
  
            // Start and end point of interval
            int w = it2->first, c = it2->second;
            if (w <= start && c >= end) {
  
                // If (w, c) is superset of (start, end),
                // merge the 2 components
                merge(u, v);
                break;
            }
        }
    }
  
    // If the interval is of length 1,
    // answer the query
    if (start == end) {
        ans[start] = nc;
        return;
    }
  
    // Recursively call the function
    int mid = (start + end) >> 1;
    solve(start, mid);
    solve(mid + 1, end);
  
    // Return the graph to the state
    // at function call
    rollback(tmp);
}
  
// Utility function to solve the problem
void componentAtInstant(vector<int> queries[])
{
    // Initially graph empty, so N components
    nc = N;
  
    for (int i = 0; i < Q; i++) {
        int t = queries[i][0];
        int u = queries[i][1], v = queries[i][2];
  
        // To standardise the procedure
        if (u > v)
            swap(u, v);
  
        if (t == 1) {
  
            // Add edge and start a new interval
            // for this edge
            graph[{ u, v }].push_back({ i, Q });
        }
        else {
  
            // Close the interval for the edge
            graph[{ u, v }].back().second = i - 1;
        }
    }
  
    // Call the function to find components
    solve(0, Q);
}
  
// Driver code
int main()
{
    N = 3, Q = 4;
    vector<int> queries[] = { { 1, 1, 2 }, { 1, 2, 3 }, { 2, 1, 2 }, { 2, 2, 3 } };
  
    // Function call
    componentAtInstant(queries);
  
    for (int i = 0; i < Q; i++)
        cout << ans[i] << " ";
  
    return 0;
}

2 1 2 3 

Complejidad de tiempo: O(Q * logQ * logN)

• Análisis: Deje que haya M aristas que existen en el gráfico inicialmente. 
  • El número total de aristas que podrían existir en el gráfico es M+Q (se agrega una arista en cada consulta; no se elimina ninguna arista).
  • El número total de operaciones de adición y eliminación de aristas es O((M+Q) log Q) y cada operación lleva un tiempo logN . 
  • En el problema anterior, M = 0 . Entonces, la complejidad temporal de este algoritmo es O(Q * logQ * logN).

Espacio Auxiliar: O(N+Q)