HackerEarth Special paths problem solution

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

coding problems solutions