Union_find_application_ (finding minimum cost's component among all disconnected components)

In this question ,firstly there are n disconnected components ,with different costs.
One -by -one, these disconnected componets are getting attached. we have to find the smallest cost
component after each attachment.

 https://www.hackerrank.com/contests/morgan-stanley-2015/challenges/min-con-com



#include<bits/stdc++.h>

using namespace std;

multiset<int> s;
multiset<int>::iterator it;

int cost[500005];
int parent[500005];
int rankk[500005];


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




void merge(int nod1,int nod2)
{
    int p1=find(nod1);
    int p2=find(nod2);

    if(rankk[p1]>rankk[p2])
    {
        parent[p2]=p1;                   ///those rankk is more ,will become parent

        it=s.find(cost[p2]);
        s.erase(it);
        it=s.find(cost[p1]);
        s.erase(it);
        cost[p1]+=cost[p2];
        s.insert(cost[p1]);

         cost[p2]=-1;                      /// '-1' will tell that this is removed
    }
    else
    {
        parent[p1]=p2;
        if(rankk[p1]==rankk[p1])
            rankk[p1]++;

        it=s.find(cost[p2]);
        s.erase(it);
        it=s.find(cost[p1]);
        s.erase(it);             /// cost of p1 and p2 will be erased and new sum cost will be inserted
        cost[p2]+=cost[p1];
        s.insert(cost[p2]);

        cost[p1]=-1;
    }
}





int main()
{
 int n,k,i,j,l,p,q;
 cin>>n>>k;

 for(i=1;i<=n;i++)
 {
    cin>>cost[i];
    s.insert(cost[i]);      /// this set will give minimum available cost at each moment (this will be the answer in this ques.)
 }


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

 for(i=1;i<=k;i++)
 {
   cin>>p>>q;

   if(find(p)!=find(q))
    {
      merge(p,q);
    }
 
    it=s.begin();
    cout<<(*it)<<endl;
 }
return 0;
}