MST_( Kruskal algo.) using Union find

Jack goes to Rapture (MST+dfs)

https://www.hackerrank.com/challenges/jack-goes-to-rapture

In this question , we have to say the minimum among ( all the paths's maximum edge cost ).

Firstly, we have to apply Kruskal algorithm to find the Minimum spanning tree. After that we find the maximum cost edge in the path from 1 (source)  to n (destination).





#include<bits/stdc++.h>

using namespace std;

vector<pair<int,int> > mst[100000];

int visited[100000];

int parent[1000000];

int rankk[1000000];

int ans=INT_MIN;



void dfs(int nod,int last,int curr)
{
    visited[nod]=1;

    if(nod==last)
    {
       ans=max(ans,curr);
       return;
    }

  for(int i=0;i<mst[nod].size();i++)
  {
     if(visited[mst[nod][i].first]==0)
      dfs(mst[nod][i].first,last,max(curr,mst[nod][i].second));
  }

  visited[nod]=0;
}





int find(int node)
{
   if(parent[node]==node)
        return node;
   else
      return find(parent[node]);
}



void merge(int node1,int node2)
{
 int x=find(node1);
 int y=find(node2);

 if(rankk[x]>rankk[y])
    parent[y]=x;
 else
 {
     parent[x]=y;
     if(rankk[x]==rankk[y])
        rankk[y]++;
 }
}




int main()
{
 int n,e,i,j,k,l,a,b,c;

 cin>>n>>k;

 vector<pair<int, pair<int,int > > > v;

 for(i=0;i<k;i++)
 {
   cin>>a>>b>>c;
   v.push_back({c,{b,a}});
 }

 sort(v.begin(),v.end());


 for(i=1;i<=n;i++)
 {
    parent[i]=i;
    rankk[i]=0;
 }

 for(i=0;i<k;i++)
 {
   if(find(v[i].second.first)!=find(v[i].second.second))
    {
     merge(v[i].second.first,find(v[i].second.second));
     mst[v[i].second.first].push_back({v[i].second.second,v[i].first});
     mst[v[i].second.second].push_back({v[i].second.first,v[i].first});
    }
 }


/// Mst is ready , now we just have to apply the dfs.

dfs(1,n,0);
if(ans==INT_MIN)
    cout<<"NO PATH EXISTS"<<endl;
else
    cout<<ans<<endl;

return 0;
}