IOI '14 P3 - Game

#include <iostream>
#include <vector>

using namespace std;

// DSU
int components;
vector<int> parent;
vector<vector<int>> questions; // between pairs of components
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];
    parent[j] = i;

    // only n unions, O(n) each, so O(n^2) in total
    int N = parent.size();
    for (int k = 0; k < N; ++k) {
        if (parent[k] < 0) {
            // these two are equal values
            questions[k][i] += questions[k][j];
            questions[i][k] += questions[j][k];
        }
    }
}

void initialize(int n) {
    parent.assign(n, -1);
    questions.assign(n, vector<int>(n));
    components = n;
}
int hasEdge(int u, int v) {
    if (components == 2) return 0;
    u = root(u), v = root(v);
    ++questions[u][v], ++questions[v][u];
    if (questions[u][v] == parent[u] * parent[v]) {
        unite(u, v);
        return 1;
    } else return 0;
}