Union-find com rollback

#include <bits/stdc++.h>
using namespace std;
vector<int> pai, sub;
int qSets = 0, temp = 0;
stack<tuple<int, int, int>> opers;

int find(int v) {return (v == pai[v] ? v : find(pai[v]));}
void une(int x, int y)
{
    x = find(x); y = find(y);
    if (x == y) {opers.emplace(-1, -1, ++temp); return;}
    if (sub[x] < sub[y]) swap(x, y);
    opers.emplace(x, y, ++temp);
    pai[y] = x; sub[x] += sub[y]; --qSets;
}
void rollback()
{
    if (opers.empty()) return;
    auto [x, y, t] = opers.top(); opers.pop();
    if (x == -1) return;
    pai[y] = y; sub[x] -= sub[y]; ++qSets;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M; cin >> N >> M;
    pai.resize(N+1); iota(pai.begin(), pai.end(), 0);
    sub.resize(N+1); fill(sub.begin(), sub.end(), 1);
    qSets = N;

    vector<int> versions;
    while (M--)
    {
        string type; cin >> type;
        if (type == "union")
        {
            int x, y;
            cin >> x >> y;
            une(x, y);
            cout << qSets << '\n';
        }
        else if (type == "persist") versions.push_back(temp);
        else //rollback
        {
            //enquanto o tempo da operacao for maior que o da versao, dou rollback
            while (!opers.empty() && get<2>(opers.top()) > versions.back()) rollback();
            versions.pop_back();
            cout << qSets << '\n';
        }
    }
}