#include "game.h"
#define N 1505
int par[N],edges[N][N],sz[N],nn;
int f(int x)
{
if(par[x]==x)
return x;
return par[x]=f(par[x]);
}
bool issameset(int x,int y)
{
int fx=f(x);
int fy = f(y);
return (fx==fy);
}
void join(int x,int y)
{
int fx = f(x);
int fy = f(y);
if(sz[fx] > sz[fy])
{
fx^=fy;
fy^=fx;
fx^=fy;
}
par[fx] = fy;
sz[fy]+=sz[fx];
for(int i = 0;i < nn;i++)
{
edges[fy][i] += edges[fx][i];
edges[fx][i] = 0;
}
for(int i = 0;i < nn;i++)
{
edges[i][fy] += edges[i][fx];
edges[i][fx] = 0;
}
return;
}
void initialize(int n)
{
nn = n;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < n;j++)
{
if(i==j)
continue;
edges[i][j]=1;
}
sz[i]=1;
par[i]=i;
}
return;
}
int hasEdge(int u, int v)
{
if(issameset(u,v))
return 0;
int fu = f(u);
int fv = f(v);
edges[fu][fv]--;
edges[fv][fu]--;
if(edges[fu][fv] == 0)
{
join(fu,fv);
return 1;
}
else
return 0;
}
