#include <bits/stdc++.h>
#include "game.h"
using namespace std;
//declaring required data objects
int nodes;
std::vector<int> node_set;
std::vector<std::list <int>> set_nodes;
std::list<int> present_sets;
std::vector<std::vector<int>> possible_connections;
void initialize(int n) {
nodes = n;
set_nodes.resize(n);
possible_connections.assign(n, std::vector<int> (n, 1));
for(int i = 0; i<n; i++) {
node_set.push_back(i);
set_nodes[i].push_back(i);
present_sets.push_back(i);
possible_connections[i][i] = 0;
}
}
int hasEdge(int u, int v) {
if(possible_connections[node_set[u]][node_set[v]] > 1) {
possible_connections[node_set[u]][node_set[v]]--;
return 0;
}
else if(possible_connections[node_set[u]][node_set[v]] == 0)
return 0;
else {
//union of node_set[u] and node_set[v]
int set1, set2;
if(set_nodes[node_set[u]].size()>set_nodes[node_set[v]].size()) {
set1 = node_set[u];
set2 = node_set[v];
}
else {
set1 = node_set[v];
set2 = node_set[u];
}
for(auto& departing_node : set_nodes[set2]) {
node_set[departing_node] = set1;
set_nodes[set1].push_back(departing_node);
}
std::list<int>::iterator to_delete;
for(std::list<int>::iterator i = present_sets.begin(); i!=present_sets.end(); i++) {
if(*i==set2)
to_delete = i;
else if(*i!=set1) {
possible_connections[set1][*i] += possible_connections[set2][*i];
possible_connections[*i][set1] += possible_connections[*i][set2];
}
}
present_sets.erase(to_delete);
possible_connections[set1][set2] = 0;
return 1;
}
}
