POI Task Monkeys

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// DSU
vector<int> parent;
vector<vector<int>> component;
int root(int i) {
    return parent[i] < 0 ? i : (parent[i] = root(parent[i]));
}
void unite(int i, int j) {
    i = root(i), j = root(j);
    if (i == j) return;
    if (parent[i] > parent[j]) swap(i, j);
    parent[i] += parent[j];
    component[i].insert(component[i].end(), component[j].begin(), component[j].end());
    parent[j] = i;
    component[j].clear();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> holding(1+n, vector<int>(2, -1));
    for (int i = 1; i <= n; ++i) cin >> holding[i][0] >> holding[i][1];
    vector<pair<int, int>> changes(m);
    for (int i = 0; i < m; ++i) {
        int monkey, hand; cin >> monkey >> hand;
        --hand;
        int &fellow = holding[monkey][hand];
        changes[i] = {monkey, fellow};
        fellow = -1;
    }

    // dsu with component members with additional log(n)
    parent.assign(1+n, -1);
    component.resize(1+n);
    for (int i = 1; i <= n; ++i) component[i] = {i};
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 2; ++j) {
            if (holding[i][j] != -1) unite(i, holding[i][j]);
        }
    }

    vector<int> groundTime(1+n);
    int r = root(1);
    for (int x : component[r]) groundTime[x] = -1;

    for (int i = (int)changes.size()-1; i >= 0; --i) {
        auto [monkey, fellow] = changes[i];
        r = root(1);
        int r1 = root(monkey), r2 = root(fellow);
        if (r1 == r2) continue;
        if (r2 == r) swap(monkey, fellow), swap(r1, r2);
        if (r1 == r) {
            for (int x : component[r2]) groundTime[x] = i;
        }
        unite(monkey, fellow);
    }
    for (int i = 1; i <= n; ++i) cout << groundTime[i] << '\n';
    return 0;
}