#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adjmat;
vector<vector<int>> numnotconn;
vector<int> ufds;
vector<int> usize;
int n;
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);
if (ra==rb){return;}
//path compression
ufds[ra]=rb;
usize[rb]+=usize[ra];
//new root: rb
for (int i = 0; i<n; i++){
numnotconn[rb][i]+=numnotconn[ra][i];
numnotconn[i][rb]+=numnotconn[i][ra];
}
}
//0 - no, 1 - yes, 2 - unchecked
void initialize(int N) {
n=N;
adjmat.resize(n,vector<int>(n,2));
numnotconn.resize(n,vector<int>(n,0));
ufds.resize(n);
usize.resize(n,1);
for (int i = 0; i<n; i++){
ufds[i]=i;
}
}
int hasEdge(int u, int v) {
int ru = root(u);
int rv = root(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;
numnotconn[ru][rv]++;
numnotconn[rv][ru]++;
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;
numnotconn[ru][rv]++;
numnotconn[rv][ru]++;
return 0;
}
}
}
if (usize[root(u)]+usize[root(v)]==n){
numnotconn[ru][rv]++;
numnotconn[rv][ru]++;
return 0;
}
if (numnotconn[ru][rv]==(usize[ru]*usize[rv]-1)){
adjmat[u][v]=1;
adjmat[v][u]=1;
connect(u,v);
return 1;
}
numnotconn[ru][rv]++;
numnotconn[rv][ru]++;
return 0;
}
