Advertisement
Guest User

Union Find

a guest
Sep 26th, 2015
187
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4. long long Weight[200013];
  5. multiset <long long> Order;
  6. long long n,q,we,from,to;
  7. long long Father[200013];
  8.  
  9. int findF(int node){
  10.     if (node==Father[node]) return node;
  11.     return Father[node]=findF(Father[node]);
  12. }
  13.  
  14. void Forest_merge(int a,int b){
  15.     int f1 = findF(a);
  16.     int f2 = findF(b);
  17.       if (f1==f2) return;
  18.       Father[a] = Father[b];
  19.       Order.erase(Order.find(Weight[f1]));
  20.       Order.erase(Order.find(Weight[f2]));
  21.       Weight[f2] += Weight[f1];
  22.       Order.insert(Weight[f2]);
  23. }
  24.  
  25. int main(void){
  26.  cin>>n>>q;
  27.  for (int i=1;i<=n;++i){
  28.   cin>>Weight[i];
  29.   Order.insert(Weight[i]);
  30.   Father[i]=i;
  31.  }
  32.  while(q--){
  33.     cin>>from>>to;
  34.     Forest_merge(from,to);
  35.     multiset<long long>::iterator it = Order.begin();
  36.     cout<<*it<<endl;
  37.  }
  38. return 0;
  39. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement