Connected Components

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pt;
typedef pair<pt, int> query;

const int MAX_N = 510;
const int MAX_Q = 100000;

bool cmp(const query& a, const query& b){
    int al = a.first.first;
    int bl = b.first.first;
    int ar = a.first.second;
    int br = b.first.second;
    if(al < bl){
        return true;
    } else if(al > bl){
        return false;
    }
    if(ar > br){
        return true;
    } else if(ar < br){
        return false;
    }
    return a.second < b.second;
}

vector<pt> edges;
query queries[MAX_Q];
int ans[MAX_Q];
int comp[MAX_N];
int sz[MAX_N];

int components = 0;

inline int ufind(int v){
    if(comp[v] == v){
        return v;
    }
    return comp[v] = ufind(comp[v]);
}

inline bool umerge(int u, int v){
    int cu = ufind(u);
    int cv = ufind(v);
    if(cu == cv){
        return false;
    }
    if(sz[cu] > sz[cv]){
        comp[cv] = cu;
        sz[cu] += sz[cv];
    } else {
        comp[cu] = cv;
        sz[cv] += sz[cu];
    }
    return true;
}

inline void addEdge(int idx){
    if(umerge(edges[idx].first, edges[idx].second)){
        components--;
    }
}

inline void init(int n){
    for(int i = 0;i<n;++i){
        comp[i] = i;
        sz[i] = 1;
    }
    components = n;
}

int main(){
    ios::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    for(int i = 0;i<m;++i){
        int x, y;
        cin>>x>>y;
        x--;y--;
        edges.push_back({x, y});
    }
    int k;
    cin>>k;
    for(int i = 0;i<k;++i){
        int l, r;
        cin>>l>>r;
        l--;r--;
        queries[i] = {{l, r}, i};
    }
    sort(queries, queries+k, cmp);
    int left = -1, right = m-1;
    init(n);
    for(int i = 0;i<k;++i){
        int l = queries[i].first.first;
        int r = queries[i].first.second;
        if(l != left){
            init(n);
            left = 0;
            right = m-1;
            while(left < l){
                addEdge(left);
                left++;
            }
        }
        while(right > r){
            addEdge(right);
            right--;
        }
        ans[queries[i].second] = components;
    }

    for(int i = 0;i<k;++i){
        cout<<ans[i]<<endl;
    }
    return 0;
}