In this HackerEarth Special paths problem solution, You are given an undirected connected graph G with N nodes and M edges. Every node has a value A[i] assigned to it.

The value of a simple path between node u and v is as follows:

The maximum absolute difference between the values of adjacent nodes present in the simple path.
Find the minimum possible path value of any simple paths between start and end nodes.

## HackerEarth Special paths problem solution.

```#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int parent[100000+1];
int size[100000+1];

int par(int u)
{
while(u != parent[u])
{
u = parent[u];
}
return u;
}

void merge(int u, int v)
{
if(size[u] < size[v])
{
parent[u] = v;
size[v] += size[u];
}
else
{
parent[v] = u;
size[u] += size[v];
}
}

void solve(){
int n, m;
cin >> n >> m;
assert(1 <= n and n <= 100000);
assert(1 <= m and m <= 100000);
vector<pair<int,int> >edge;
for(int i = 1 ; i <= m ; i++)
{
int u, v;
cin >> u >> v;
assert(u != v);
assert(1 <= u and u <= n);
assert(1 <= v and v <= n);
edge.push_back(make_pair(u,v));
}

int value[n+1];
for(int i = 1 ; i <= n ; i++){
cin >> value[i];
assert(1 <= value[i] and value[i] <= 1000000);
}

int start, end;
cin >> start >> end;

int s = 1;
int e = 1000000;
int ans = -1;

while(s <= e)
{
int mid = (s + e) >> 1;

for(int i = 1 ; i <= n ; i++)
{
parent[i] = i;
size[i] = 1;
}

for(int i = 0 ; i < m ; i++)
{
int u = edge[i].first;
int v = edge[i].second;

int pu = par(u);
int pv = par(v);

int val = abs(value[u] - value[v]);

if(val > mid) continue;

if(pu != pv){
merge(pu,pv);
}
}

if(par(start) == par(end))
{
ans = mid;
e = mid - 1;
}
else
{
s = mid + 1;
}
}

cout << ans << endl;
}

int main(){
int t = 1;
while(t--)
{
solve();
}
}```

### Second solution

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 14;
struct Dsu{
int par[maxn];
Dsu(){  memset(par, -1, sizeof par);  }
int root(int v){
return par[v] < 0 ? v : par[v] = root(par[v]);
}
bool fri(int v, int u){
return root(v) == root(u);
}
bool merge(int v, int u){
if((v = root(v)) == (u = root(u)))
return 0;
par[u] += par[v];
par[v] = u;
return 1;
}
}  dsu;

int n, m, v[maxn], u[maxn], a[maxn];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> v[i] >> u[i];
v[i]--, u[i]--;
}
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int s, e;
cin >> s >> e;
s--, e--;
int lo = -1, hi = 1e6;
while(hi - lo > 1){
dsu = Dsu();
int mid = (lo + hi) / 2;
for (int i = 0; i < m; ++i) {
if(abs(a[v[i]] - a[u[i]]) <= mid)
dsu.merge(v[i], u[i]);
}
(dsu.fri(s, e) ? hi : lo) = mid;
}
cout << hi << '\n';
}```