#include "game.h"
#include <bits/stdc++.h>
struct UnionFind {
int n;
std::vector<int> data;
std::vector<std::vector<int>> edges;
UnionFind(int n_) : n(n_) {
edges.resize(n, std::vector<int>(n, 1));
data.assign(n, -1);
}
int find(int v) {
if (data[v] < 0) {
return v;
} else {
return data[v] = find(data[v]);
}
}
int groupSize(int v) {
return -data[find(v)];
}
bool merge(int a, int b) {
a = find(a);
b = find(b);
assert(edges[a][b] == edges[b][a]);
--edges[a][b];
--edges[b][a];
if (a == b) {
return false;
}
if (edges[a][b] != 0) {
return false;
}
if (groupSize(a) < groupSize(b)) {
std::swap(a, b);
}
data[a] += data[b];
data[b] = a;
// edge
for (int i = 0; i < n; ++i) {
if (find(i) != i) {
continue;
}
if (i == a or i == b) {
continue;
}
edges[a][i] += edges[b][i];
edges[i][a] += edges[i][b];
}
return true;
}
};
UnionFind uft(0);
void initialize(int n) {
uft = UnionFind(n);
}
int hasEdge(int u, int v) {
return uft.merge(u, v);
}
