Encuentre el peso del árbol de expansión mínimo

Dado un gráfico ponderado no dirigido conectado con N Nodes y M aristas . La tarea es realizar consultas dadas y encontrar el peso del árbol de expansión mínimo. Las consultas son de tres tipos: 
 

1. consulta (1) -> Encuentra el peso del árbol de expansión mínimo.
2. query(2, x, y) -> Cambia el peso del borde entre los Nodes x e y a 0 .
3. query(3, x, y) -> Restaurar el peso del borde entre los Nodes x e y a su peso original .

Ejemplos: 
 

Aporte: 
 

consulta(2, 1, 2), 
consulta(1), 
consulta(3, 1, 2), 
consulta(1) 
Salida: 
2 
3
Entrada: 
 

consulta (1), 
consulta (2, 3, 4), 
consulta (1) 
Salida: 
4 
2 
 

Enfoque: primero calculemos el MST del gráfico inicial antes de realizar cualquier consulta y sea T este MST. La observación crucial es que en cualquier punto mientras se manejan las consultas, el peso del MST del gráfico actual se puede calcular ejecutando el algoritmo de Kruskal en los bordes con peso cero en este punto y los bordes de T. Por lo tanto, mantenga los bordes con peso cero en una estructura de datos y después de la consulta de tipo 2 y tipo 3, calcule el peso del árbol de expansión mínimo.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 2005
 
// To store vertices, edges
// and the required answer
int n, m, ans;
 
// To store parent and rank
int par[N], Rank[N];
 
// To store edges and the edges in MST
vector<pair<int, pair<int, int> > > edges, mst;
 
// To store the edges with weight zero
queue<pair<int, int> > zeros;
 
// Function for initialize
void initialize()
{
    for (int i = 0; i <= n; i++) {
        par[i] = i;
        Rank[i] = 0;
    }
}
 
// Function to add edges
void Add_edge(int u, int v, int weight)
{
    edges.push_back({ weight, { u, v } });
}
 
// Utility function to find set of an element i
// (uses path compression technique)
int find(int x)
{
    if (par[x] != x)
        par[x] = find(par[x]);
 
    return par[x];
}
 
// Function that performs union of two sets x and y
// (uses union by rank)
void Union(int x, int y)
{
    int xroot = find(x);
    int yroot = find(y);
 
    if (Rank[xroot] < Rank[yroot])
        par[xroot] = yroot;
    else if (Rank[xroot] > Rank[yroot])
        par[yroot] = xroot;
    else {
        par[yroot] = xroot;
        Rank[xroot]++;
    }
}
 
// Function to compute minimum spanning tree
void compute_MST()
{
    // Sort edges in increasing order of weight
    sort(edges.begin(), edges.end());
 
    // Go through all the edges
    for (int i = 0; i < m; i++) {
        int u = find(edges[i].second.first);
        int v = find(edges[i].second.second);
 
        if (u == v)
            continue;
 
        // Build minimum spanning tree
        // and store minimum cost
        mst.push_back(edges[i]);
        ans += edges[i].first;
        Union(u, v);
    }
}
 
// Function to find the cost of minimum
// spanning tree
void Modified_Kruskal(pair<int, int> x)
{
    initialize();
 
    // Make answer zero
    ans = 0;
    int sz = zeros.size();
 
    // Keep the edges which only have zero weights
    // and remove all the other edges
    for (int i = 0; i < sz; i++) {
        pair<int, int> Front = zeros.front();
        zeros.pop();
 
        if (Front.first == x.first
            and Front.second == x.second)
            continue;
 
        // Make union between the vertices of
        // edges which have weight zero and keep
        // them in queue
        Union(Front.first, Front.second);
        zeros.push(Front);
    }
 
    // Find the cost of the minimum spanning tree
    for (int i = 0; i < mst.size(); i++) {
        int u = find(mst[i].second.first);
        int v = find(mst[i].second.second);
 
        if (u == v)
            continue;
 
        ans += mst[i].first;
        Union(u, v);
    }
}
 
// Function to handle different queries
void query(int type, int u = 0, int v = 0)
{
 
    // Update edge weight to 0
    if (type == 2) {
        // push edge in zeros
        zeros.push({ u, v });
        Modified_Kruskal({ -1, -1 });
    }
 
    // Restore edge weight to original value
    else if (type == 3) {
        // push edge in zeros
        zeros.push({ u, v });
        Modified_Kruskal({ u, v });
    }
    else
        cout << ans << endl;
}
 
// Driver code
int main()
{
 
    // Number of nodes and edges
    n = 4, m = 4;
    initialize();
 
    // Add edges
    Add_edge(1, 2, 1);
    Add_edge(2, 3, 1);
    Add_edge(3, 4, 1);
    Add_edge(4, 1, 1);
 
    // Build the minimum spanning tree
    compute_MST();
 
    // Execute queries
    query(2, 1, 2);
    query(1);
    query(3, 1, 2);
    query(1);
 
    return 0;
}

# Python3 implementation of the approach
from collections import deque
 
N = 2005
 
# To store vertices, edges
# and the required answer
n, m, ans = 0, 0, 0
 
# To store parent and rank
par = [0] * N
Rank = [0] * N
 
# To store edges and the edges in MST
edges, mst = [], []
 
# To store the edges with weight zero
zeroes = deque()
 
# Function for initialize
def initialize():
    for i in range(n + 1):
        par[i] = i
        Rank[i] = 0
 
# Function to add edges
def add_edge(u: int, v: int, weight: int):
    edges.append((weight, (u, v)))
 
# Utility function to find set of an element i
# (uses path compression technique)
def find(x: int) -> int:
    if par[x] != x:
        par[x] = find(par[x])
    return par[x]
 
# Function that performs union of two sets x and y
# (uses union by rank)
def union(x: int, y: int):
    xroot = find(x)
    yroot = find(y)
 
    if Rank[xroot] < Rank[yroot]:
        par[xroot] = yroot
    elif Rank[xroot] > Rank[yroot]:
        par[yroot] = xroot
    else:
        par[yroot] = xroot
        Rank[xroot] += 1
 
# Function to compute minimum spanning tree
def compute_MST():
    global ans
 
    # Sort edges in increasing order of weight
    edges.sort()
 
    # Go through all the edges
    for i in range(m):
        u = find(edges[i][1][0])
        v = find(edges[i][1][1])
 
        if u == v:
            continue
 
        # Build minimum spanning tree
        # and store minimum cost
        mst.append(edges[i])
        ans += edges[i][0]
        union(u, v)
 
# Function to find the cost of minimum
# spanning tree
def modified_kruskal(x):
    global ans
    initialize()
 
    # Make answer zero
    ans = 0
    sz = len(zeroes)
 
    # Keep the edges which only have zero weights
    # and remove all the other edges
    for i in range(sz):
        front = zeroes[0]
        zeroes.popleft()
 
        if front[0] == x[0] and front[1] == x[1]:
            continue
 
        # Make union between the vertices of
        # edges which have weight zero and keep
        # them in queue
        union(front[0], front[1])
        zeroes.append(front)
 
    # Find the cost of the minimum spanning tree
    for i in range(len(mst)):
        u = find(mst[i][1][0])
        v = find(mst[i][1][1])
 
        if u == v:
            continue
        ans += mst[i][0]
        union(u, v)
 
# Function to handle different queries
def query(type: int, u=0, v=0):
    global ans
 
    # Update edge weight to 0
    if type == 2:
 
        # push edge in zeros
        zeroes.append((u, v))
        modified_kruskal((-1, -1))
 
    # Restore edge weight to original value
    elif type == 3:
 
        # push edge in zeros
        zeroes.append((u, v))
        modified_kruskal((u, v))
    else:
        print(ans)
 
# Driver Code
if __name__ == "__main__":
 
    # Number of nodes and edges
    n = 4
    m = 4
    initialize()
 
    # Add edges
    add_edge(1, 2, 1)
    add_edge(2, 3, 1)
    add_edge(3, 4, 1)
    add_edge(4, 1, 1)
 
    # Build the minimum spanning tree
    compute_MST()
 
    # Execute queries
    query(2, 1, 2)
    query(1)
    query(3, 1, 2)
    query(1)
 
# This code is contributed by
# sanjeev2552

2
3

Complejidad de tiempo: O(N) por consulta, donde N es el número total de Nodes en el gráfico.
Espacio Auxiliar: O(N)