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}$ server is located at coordinate

$(x[i],y[i])$.

The cost of connecting any two servers indexed

$i$ and

$j$ is

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

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

Given the arrays

$x$ and

$y$ of

$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.

The first line contains an integer

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

The second line contains

$n$ space separated integers where

${i}_{th}$ integer denotes

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

$1\le i\le n$.

The third line contains

$n$ space separated integers where

${i}_{th}$ integer denotes

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

$1\le i\le n$.

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

3 2 4 8 6 10 9

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;
}
```

## Leave a Reply