#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
struct DSU
{
vector<int> e;
DSU(int n)
{
e.assign(n , -1);
}
int get(int u )
{
return (e[u] < 0 ? u : e[u] = get(e[u]));
}
bool same(int u , int v)
{
return get(u) == get(v);
}
bool unite(int u , int v)
{
u = get(u ) , v =get(v);
if(u == v)
return 0;
if(e[u] > e[v])
swap(u , v);
e[u]+=e[v];
e[v] = u;
return 1;
}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n= (int)x.size();
vector<int> u , v , a , b;
map<pair<int, int> , int> idx;
set<pair<int ,int>> taken;
for(int i = 0 ; i <n ; i++)
{
idx[{x[i] , y[i]}] = i;
}
vector<pair<int ,int>> vv;
for(int i = 0 ; i < n ; i++)
vv.push_back({x[i] , y[i]});
sort(vv.begin() , vv.end() , [](pair<int, int> a , pair<int ,int> b){return a.first + a.second < b.first + b.second;});
u.clear();
v.clear();
a.clear();
b.clear();
taken.clear();
for(int i = 0 ; i < n ;i++)
{
x[i] = vv[i].first , y[i] = vv[i].second;
}
DSU dsu(n);
for(int i = 0 ; i < n ;i++)
{
if(idx.count({x[i] + 2 , y[i]}) && dsu.unite(idx[{x[i] , y[i]}] , idx[{x[i] + 2 , y[i]}]))
{
if(!taken.count({x[i] + 1 , y[i] - 1}))
{
u.push_back(idx[{x[i] , y[i]}]);
v.push_back(idx[{x[i] + 2 , y[i]}]);
a.push_back(x[i] + 1);
b.push_back(y[i] - 1);
taken.insert({x[i] + 1 , y[i] - 1});
}
else if(!taken.count({x[i] + 1 , y[i] + 1}))
{
u.push_back(idx[{x[i] , y[i]}]);
v.push_back(idx[{x[i] + 2 , y[i]}]);
a.push_back(x[i] + 1);
b.push_back(y[i] + 1);
taken.insert({x[i] + 1 , y[i] + 1});
}
}
if(idx.count({x[i] , y[i] + 2}) && dsu.unite(idx[{x[i] , y[i]}] , idx[{x[i] , y[i] + 2}]))
{
if(!taken.count({x[i] - 1 , y[i] + 1}))
{
u.push_back(idx[{x[i] , y[i]}]);
v.push_back(idx[{x[i] , y[i] + 2}]);
b.push_back(y[i] + 1);
a.push_back(x[i] - 1);
taken.insert({x[i] - 1 , y[i] +1});
}
else if(!taken.count({x[i] + 1 , y[i] + 1}))
{
u.push_back(idx[{x[i] , y[i]}]);
v.push_back(idx[{x[i] , y[i] + 2}]);
b.push_back(y[i] + 1);
a.push_back(x[i] + 1);
taken.insert({x[i] + 1 , y[i] +1});
}
}
}
set<int> s;
for(int i = 0 ;i < n ;i++)
{
s.insert(dsu.get(i));
}
if((int)s.size() == 1)
{
build(u , v , a , b);
return 1;
}
return 0;
}
