Shared code

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

struct weightedDSU{
    vector<int> parent, weight, index;
    int numComponents;
    
    weightedDSU(int n) : parent(n), weight(n), index(n), numComponents(n) {
        for(int i = 0; i < n; i++){
            parent[i] = i;
            index[i] = rand();
        }
    }
    
    int getRoot(int v, int w = 1){
        while(weight[v] >= w){
            while(weight[parent[v]] >= weight[v])
                parent[v] = parent[parent[v]];
            v = parent[v];
        }
        return v;
    }
    
    void addEdgeHelper(int u, int v, int w){
        while(u != v){
            u = getRoot(u, w);
            v = getRoot(v, w);
            if(index[u] < index[v])
                swap(u, v);
            int temp_parent = parent[v], temp_weight = weight[v];
            parent[v] = u;
            weight[v] = w;
            u = temp_parent;
            w = temp_weight;
        }
    }
    
    int mainEdge(int u, int v){
        if(getRoot(u) != getRoot(v))
            return -1;
        while(u != parent[v] && v != parent[u]){
            if(weight[u] > weight[v])
                u = parent[u];
            else
                v = parent[v];
        }
        if(u == parent[v])
            return v;
        else
            return u;
    }
    
    void addEdge(int u, int v, int w){
        if(u == v)
            return;
        int p = mainEdge(u, v);
        if(p == -1){
            numComponents--;
            addEdgeHelper(u, v, w);
        }
        else if(w > weight[p]){
            parent[p] = p;
            weight[p] = 0;
            addEdgeHelper(u, v, w);
        }
    }
    
    void deleteEdge(int u, int v, int w){
        while(parent[v] != v){
            if(weight[v] == w){
                parent[v] = v;
                weight[v] = 0;
                numComponents++;
                return;
            }
            while(weight[parent[v]] >= weight[v])
                parent[v] = parent[parent[v]];
            v = parent[v];
        }
        while(parent[u] != u){
            if(weight[u] == w){
                parent[u] = u;
                weight[u] = 0;
                numComponents++;
                return;
            }
            while(weight[parent[u]] >= weight[u])
                parent[u] = parent[parent[u]];
            u = parent[u];
        }
    }
};

struct edge{
    int u, v, w;
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    vector<edge> edges(m + k);
    unordered_map<unsigned int, int> edgeMap;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        if(a > b)
            swap(a, b);
        edges[i] = {a, b, m + k};
        edgeMap[(a - 1) * n + b] = i;
    }
    for(int i = 0; i < k; i++){
        int t, a, b;
        cin >> t >> a >> b;
        if(a > b)
            swap(a, b);
        if(t == 1){
            edges[m + i] = {a, b, m + k};
            edgeMap[(a - 1) * n + b] = m + i;
        }
        if(t == 2){
            edges[m + i] = {a, b, -1};
            edges[edgeMap[(a - 1) * n + b]].w = m + i;
        }
    }
    weightedDSU mst(n + 1);
    for(int i = 0; i < m; i++)
        mst.addEdge(edges[i].u, edges[i].v, edges[i].w);
    cout << mst.numComponents - 1 << ' ';
    for(int i = 0; i < k; i++){
        if(edges[m + i].w == -1)
            mst.deleteEdge(edges[m + i].u, edges[m + i].v, m + i);
        else
            mst.addEdge(edges[m + i].u, edges[m + i].v, edges[m + i].w);
        cout << mst.numComponents - 1 << ' ';
    }
}