#include "game.h"
#include <random>
#include <time.h>
#include <algorithm>
const int SIZ = 39;
const int MAXN = SIZ * SIZ;
bool viz[SIZ];
struct Component {
int adj[SIZ][SIZ];
int n;
void init( int N ) {
n = N;
for( int i = 0 ; i < n ; i++ ){
for( int j = 0 ; j < n ; j++ )
adj[i][j] = 1;
adj[i][i] = 0;
}
}
void remove_edge( int u, int v ) { adj[u][v] = adj[v][u] = 0; }
void insert_edge( int u, int v ) { adj[u][v] = adj[v][u] = 1; }
void dfs( int u ) {
viz[u] = true;
for( int v = 0 ; v < n ; v++ )
if( !viz[v] && adj[u][v] )
dfs( v );
}
bool connected( int u, int v ) {
for( int i = 0 ; i < n ; i++ )
viz[i] = false;
dfs( u );
return viz[v];
}
};
namespace Solver {
Component local[SIZ];
int csiz[SIZ];
Component global;
int comp[MAXN];
int comp_idx[MAXN];
int edge_tracker[SIZ][SIZ];
int n;
int ncomp;
void init( int N ) {
n = N;
std::mt19937 rng( clock() );
for( int i = 0 ; i < n ; i++ ){
comp[i] = i / SIZ;
comp_idx[i] = i % SIZ;
csiz[comp[i]]++;
}
for( int i = 0 ; i + 1 < n ; i++ ){
int j = i + rng() % (n - i);
std::swap( comp[i], comp[j] );
std::swap( comp_idx[i], comp_idx[j] );
}
ncomp = (n - 1) / SIZ + 1;
for( int i = 0 ; i < ncomp ; i++ )
local[i].init( csiz[i] );
global.init( ncomp );
for( int i = 0 ; i < ncomp ; i++ )
for( int j = i + 1 ; j < ncomp ; j++ )
edge_tracker[i][j] = edge_tracker[j][i] = csiz[i] * csiz[j];
}
bool query( int u, int v ) {
// problema locala?
if( comp[u] == comp[v] ) {
int C = comp[u];
int a = comp_idx[u], b = comp_idx[v];
local[C].remove_edge( a, b );
if( local[C].connected( a, b ) )
return false;
local[C].insert_edge( a, b );
return true;
}
// problema globala
int U = comp[u], V = comp[v];
if( edge_tracker[U][V] > 1 ){
edge_tracker[U][V]--;
return false;
}
global.remove_edge( U, V );
if( global.connected( U, V ) )
return false;
global.insert_edge( U, V );
return true;
}
}
void initialize( int n ) { Solver::init( n ); }
int hasEdge( int u, int v ) { return Solver::query( u, v ); }
