#include "game.h"
#include <vector>
#include <set>
const int NMAX = 1000;
int n;
int p[NMAX];
int canAdd[NMAX];
int root(int u) {
return p[u] == u? u : p[u] = root(p[u]);
}
void join(int u, int v) {
u = root(u);
v = root(v);
p[u] = v;
canAdd[v] += canAdd[u];
canAdd[v] -= 2; // (u, v) nu il mai numar nici din partea lui u, nici din partea lui v
}
void initialize(int N) {
n = N;
for (int i = 0; i < n; i++) {
canAdd[i] = n - 1;
p[i] = i;
}
}
int hasEdge(int u, int v) {
u = root(u);
v = root(v);
if (u == v) {
return 0;
}
if (canAdd[u] == 1 || canAdd[v] == 1) {
join(u, v);
return 1;
}
canAdd[u]--;
canAdd[v]--;
return 0;
}
/*
strategie:
fie E muchiile pe care le-am a daugat deja si E' muchiile pe care inca nu le am ales
daca E U E' NU formeaza spanning tree => am pierdut
fie E'' = E' \ {(u, v)} unde (u, v) e muchia curenta de la query
daca E'' U E imi da spanning tree => nu pun (u, v) in E
altfel pun (u, v) in E
asta sa fie oare singuru algoritm corect?
cred ca DA
deci trebuie doar sa vad cum optimizez
*/
