IOI '12 P2 - Parachute Rings (Standard I/O)

#include <iostream>
#include <vector>

using namespace std;

int root(int i, vector<int> &parent) {
    return parent[i] < 0 ? i : (parent[i] = root(parent[i], parent));
}
bool unite(int i, int j, vector<int> &parent) {
    i = root(i, parent), j = root(j, parent);
    if (i == j) return false;
    if (parent[i] > parent[j]) swap(i, j);
    parent[i] += parent[j];
    parent[j] = i;
    return true;
}

int main() {
    int n, l;
    cin >> n >> l;
    vector<int> parent[4];
    parent[0] = vector<int>(1+n, -1);
    bool valid[4]{};

    vector<vector<int>> degree(1+n);
    vector<pair<int, int>> edgeList;
    bool deg3 = false; // exists node with degree >= 3
    vector<int> badRoots; // roots with cycles - only used when deg3 == false
    int candidates = -1; // how many "parent" vectors are being used (only relevant when deg3 == true)
    vector<int> cand; // candidates

    auto addEdge = [&parent, &valid, &degree, &cand](int c, int u, int v) { // c is index of which parent (dsu) to add to
        if (!unite(u, v, parent[c])) valid[c] = false;
        int du = 0, dv = 0; // degrees excluding candidate node
        for (int w : degree[u]) du += w != cand[c];
        for (int w : degree[v]) dv += w != cand[c];
        if (du == 3 || dv == 3) valid[c] = false;
    };

    while (l--) {
        int x; cin >> x;
        if (x == -1) {
            if (!deg3) {
                if (badRoots.empty()) cout << n << '\n';
                else if (badRoots.size() == 1) cout << -parent[0][badRoots[0]] << '\n';
                else cout << 0 << '\n';
            } else {
                int ans = 0;
                for (int c = 0; c < candidates; ++c) ans += valid[c];
                cout << ans << '\n';
            }
        } else {
            int y; cin >> y;
            degree[x].push_back(y), degree[y].push_back(x);
            edgeList.emplace_back(x, y);
            if (!deg3) {
                if (!unite(x, y, parent[0])) badRoots.push_back(root(x, parent[0]));
                if (degree[x].size() == 3 || degree[y].size() == 3) {
                    deg3 = true;
                    if (degree[x].size() == 3 && degree[y].size() == 3) {
                        candidates = 2;
                        cand.push_back(x);
                        cand.push_back(y);
                    } else {
                        candidates = 4;
                        if (degree[y].size() == 3) swap(x, y);
                        cand.push_back(x);
                        for (int z : degree[x]) cand.push_back(z);
                    }
                    // Now construct the new "parent" arrays using the memorized edges
                    for (int c = 0; c < candidates; ++c) {
                        parent[c] = vector<int>(1+n, -1);
                        valid[c] = true;
                        for (auto [u, v] : edgeList) {
                            if (cand[c] != u && cand[c] != v) addEdge(c, u, v);
                        }
                    }
                }
            } else {
                for (int c = 0; c < candidates; ++c) {
                    if (cand[c] != x && cand[c] != y) addEdge(c, x, y);
                }
            }
        }
    }
    return 0;
}