Minimum Connected Component

Minimum Connected Component

Problem Statement

You are given N nodes. Nodes are numbered as 1, 2, 3,…, N. The weight of ith node is Wi. Initially, none of the nodes are connected by edges. You are given Q queries where each query is an Update-type query.

Each query contains two integers U and V. On executing a query, you have to add an edge between the nodes U and V. After the update you have to find the connected componentthat has minimum total weight. The total weight of a connected component is defined as the sum of weights of all the nodes in the connected component.

Constraints

• 1≤N≤2×105
• 1≤Q≤3×105
• 1≤Wi≤103
• 1≤U,V≤N
• U≠V

Input Format

First line contains two space separated integers N and Q. Second line contains N space separated integers, ith integers denotes the value of Wi. Each of the next Q line contains two space separated integers U and V.

Output Format

Print the minimum total weight after each query in separate lines.

Sample Input

5 5
4 6 4 6 5
1 2
3 4
2 5
1 5
5 3

Sample Output

4
5
10
10
25

Explanation

In the given test case, 
weight of node 1 is 4, 
weight of node 2 is 6, 
weight of node 3 is 4, 
weight of node 4 is 6, and 
weight of node 5 is 5.

1. connected components are {1, 2}, {3}, {4} and {5}. Minimum total weight is for {3} = 4.
2. connected components are {1, 2}, {3, 4} and {5}. Minimum total weight is for {5} = 5.
3. connected components are {1, 2, 5} and {3, 4}. Minimum total weight is for {3, 4} = 4+6=10.
4. connected components are {1, 2, 5} and {3, 4}. Minimum total weight is for {3, 4} = 4+6=10.
5. there is one connected component {1, 2, 3, 4, 5}. Minimum total weight is for {1, 2, 3, 4, 5} = 4+6+4+6+5=25.

---------------------------------------editorial------------------------------

Using DSU, after each operation we can have connected components.

Let's have a multiset of weights of connected components. Initially, it is weight of each node. When two connected component is mergered, both weights will be deleted form multiset and sum of them will be inserted. For example, if weights are X and Y, C++ code will be like:

mymultiset.erase(mymultiset.find(X));
mymultiset.erase(mymultiset.find(Y));
mymultiset.insert(X+Y);

after each operation you have to print minimum element in this multiset. (it's possible to use any binary tree instead multset)

-----------------------------------------EDITORIAL-----------------------------------

#include<iostream>

#include<stdio.h>

#include<vector>

typedef long long int lli;

#include<bits/stdc++.h>

#include<algorithm>

using namespace std;

int abcd[300010];

int parent[300010];

lli cost[10000000];

multiset<lli> s;

int find(int node)

{

int k;

     if(parent[node]==node)

     {

   return node;

     }

     else

      k=  find(parent[node]);

   return k;

     

}

int merge(int a, int  b)

{

multiset<lli> :: iterator ite;

  int x=find(a);

  int y=find(b);

  if(abcd[x]>abcd[y])

  {

      parent[y]=x;

      ite=s.find(cost[y]);

       s.erase(ite);

        ite=s.find(cost[x]);

       s.erase(ite);

      cost[x]+=cost[y];

      s.insert(cost[x]);

     

      cost[y]=-1;

   

  }

  else

  {

      parent[x]=y;

   if(abcd[x]==abcd[y])

   abcd[y]++;

    ite=s.find(cost[y]);

       s.erase(ite);

        ite=s.find(cost[x]);

       s.erase(ite);

   cost[y]+=cost[x];

     s.insert(cost[y]);

      cost[x]=-1;

  }

  multiset<lli >:: iterator it;

 //  cout<<" containt of set "<<endl;

  /* for(it=s.begin();it!=s.end();it++)

    {

    cout<<*it<<" ";

}

cout<<endl;*/

return 0;

}

int main()

{

 int n;

 int m;

 cin>>n;

 cin>>m;

 for(int i=0;i<n;i++)

  {

   cin>>cost[i];

   s.insert(cost[i]);

  }

 for(int i=1;i<=n;i++)

 {

    parent[i]=i;

    abcd[i]=0;

 }

 for(int i=0;i<m;i++)

 {

         int a,b;

          cin>>a>>b;

          a-=1;

          b-=1;

          if(find(a)!=find(b))

           {

            merge(a,b);

              

            //    s.erase(*it);

  }

  multiset<lli> :: iterator it;

               it=s.begin();

                cout<<*it<<endl;

 }

 return 0;

}