#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adjmat;
vector<int> ufds;
vector<int> usize;
int root(int i){
if (ufds[i]==i){
return i;
} else {
return ufds[i]=root(ufds[i]);
}
}
void connect(int a, int b){
int ra = root(a);
int rb = root(b);
//path compression
ufds[ra]=rb;
usize[rb]+=usize[ra];
}
int n;
//0 - no, 1 - yes, 2 - unchecked
void initialize(int N) {
n=N;
adjmat.resize(n,vector<int>(n,2));
ufds.resize(n);
usize.resize(n,1);
for (int i = 0; i<n; i++){
ufds[i]=i;
}
}
int hasEdge(int u, int v) {
//check neighbours of u
//cout<<u<<" "<<v<<'\n';
for (int i = 0; i<n; i++){
if (i==u||i==v){continue;}
if (adjmat[u][i]==1){
//cout<<"neighbour "<<i<<'\n';
if (adjmat[i][v]==2){
//must put 0
adjmat[u][v]=0;
adjmat[v][u]=0;
return 0;
}
}
if (adjmat[v][i]==1){
//cout<<"neighbour "<<i<<'\n';
if (adjmat[i][u]==2){
//must put 0
adjmat[u][v]=0;
adjmat[v][u]=0;
return 0;
}
}
}
if (usize[root(u)]+usize[root(v)]>=n-1){
return 0;
}
adjmat[u][v]=1;
adjmat[v][u]=1;
connect(u,v);
return 1;
}
