# Network Construction DSA Problem Solution Network Construction DSA Problem Solution

In this post, we are going to solve Network Construction DSA Problem from Standard Chartered, On-Campus Questions. Let’s have a look at the problem statement first and then try to solve the problem.

## Network Construction DSA Problem Statement

The developers of Hackerland want to construct a network of servers across the country to scale their applications. The country of Hackerland can be represented as a large coordinate grid and the developers have installed n servers across the country. The

${i}_{th}$$i_{th}$ server is located at coordinate

$\left(x\left[i\right],y\left[i\right]\right)$$(x[i],y[i])$.

The cost of connecting any two servers indexed

$i$$i$ and

$j$$j$ is

$min\left(|x\left[i\right]-x\left[j\right]|,|y\left[i\right]-y\left[j\right]|\right)$$min( |x[i]-x[j]|,|y[i]-y[j]| )$ where

$|a|$$|a|$ represents the absolute value of an integer a.

Given the arrays

$x$$x$ and

$y$$y$ of

$n$$n$ integers each, find the minimum cost of constructing the network such that every server is reachable by every other server via some direct or indirect connections.

Input

The first line contains an integer

$1\le n\le {10}^{5}$$1\le n \le 10^{5}$ denoting number of servers.

The second line contains

$n$$n$ space separated integers where

${i}_{th}$$i_{th}$ integer denotes

$1\le x\left[i\right]\le {10}^{9}$$1\le x[i] \le 10^{9}$, where

$1\le i\le n$$1\le i \le n$.

The third line contains

$n$$n$ space separated integers where

${i}_{th}$$i_{th}$ integer denotes

$1\le y\left[i\right]\le {10}^{9}$$1\le y[i] \le 10^{9}$, where

$1\le i\le n$$1\le i \le n$.

Output

Output the minimum possible cost to construct the network such that every server is reachable from every other server

Example
Input
3
2 4 8
6 10 9
Output
3


## DSA Problem Solution in C++:

#include <bits/stdc++.h>
using namespace std;

vector<int>par,sz;

void make(int n){
for(int i=0;i<n;i++){
par[i]=i;
sz[i]=1;
}
}
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void Union(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
swap(x,y);
par[y]=par[x];
sz[x]+=sz[y];
}
}

int main() {

int n;cin>>n;
vector<pair<int,int>>x,y;
for(int i=0;i<n;i++){
int a;cin>>a;
x.push_back({a,i});
}
for(int i=0;i<n;i++){
int b;cin>>b;
y.push_back({b,i});
}
sort(x.begin(),x.end());
sort(y.begin(),y.end());
vector<pair<int,pair<int,int>>>graph;
for(int i=0;i<n-1;i++){
graph.push_back({abs(x[i].first-x[i+1].first),{x[i].second,x[i+1].second}});
graph.push_back({abs(y[i].first-y[i+1].first),{y[i].second,y[i+1].second}});
}
sort(graph.begin(),graph.end());
par.resize(n);
sz.resize(n,0);
make(n);
long long cost=0;
for(auto it:graph){
int w=it.first;
int u=it.second.first;
int v=it.second.second;
if(find(u)!=find(v)){
Union(u,v);
cost+=w;

}
}
cout<<cost;
return 0;

}