HackerEarth Merge the groups problem solution

In this HackerEarth Merge the group’s problem solution You are given an array A of N elements. Each element belongs to its own group initially.

You need to process the following two types of queries:

X Y – The array elements which are at positions X and Y in array A merge their group.
X – Print the maximum absolute difference of the array values that belong to the group of Xth elements of the array.

Topics we are covering

HackerEarth Merge the group’s problem solution.

#include<bits/stdc++.h>
#define ll long long int
#define P 1000000007
#define endl "n"
using namespace std;
template<class T>   
class UnionSet{
    struct subset{
        T parent;
        T ranked;
        T max;
        T min;
    };
    struct subset *subsets;
    T size;

    public:
        UnionSet(T size){
            this->size = size;
            this->subsets = (struct subset*)malloc((size+1)*sizeof(struct subset)); 
            for (T i = 0; i <= size; i++) { 
                this->subsets[i].parent = i; 
                this->subsets[i].ranked = 0;
            }
        }

        UnionSet(vector<T> &arr){
            this->size = arr.size();
            this->subsets = (struct subset*)malloc((size+1)*sizeof(struct subset)); 
            for (T i = 0; i < this->size; i++) { 
                this->subsets[i+1].parent = i+1; 
                this->subsets[i+1].ranked = 0;
                this->subsets[i+1].max = arr[i];
                this->subsets[i+1].min = arr[i];
            }   
        }

        T findRank(T index){
            T root = findParent(index);
            return this->subsets[root].ranked;
        }

        bool isConnected(T x, T y){
            T xroot = findParent(x);
            T yroot = findParent(y);
            if (xroot == yroot)
                return true;
            else
                return false;
        }

        T findParent(T index){
            if (this->subsets[index].parent != index) 
                this->subsets[index].parent = findParent(this->subsets[index].parent); 
            return this->subsets[index].parent; 
        }

        T getAbsDifference(T index){
            T parent_idx = findParent(index);
            return abs(this->subsets[parent_idx].max - this->subsets[parent_idx].min);
        }

        void unionOperation(T x, T y){ 
            T xroot = findParent(x);
            T yroot = findParent(y);
            if (this->subsets[xroot].ranked < this->subsets[yroot].ranked){
                this->subsets[xroot].parent = yroot;
                this->subsets[yroot].max = max(this->subsets[yroot].max, this->subsets[xroot].max);
                this->subsets[yroot].min = min(this->subsets[yroot].min, this->subsets[xroot].min);
            }
            else if (this->subsets[xroot].ranked > this->subsets[yroot].ranked){
                this->subsets[yroot].parent = xroot;
                this->subsets[xroot].max = max(this->subsets[xroot].max, this->subsets[yroot].max);
                this->subsets[xroot].min = min(this->subsets[xroot].min, this->subsets[yroot].min);
            }
            else{ 
                this->subsets[yroot].parent = xroot;
                this->subsets[xroot].ranked++;
                this->subsets[xroot].max = max(this->subsets[xroot].max, this->subsets[yroot].max);
                this->subsets[xroot].min = min(this->subsets[xroot].min, this->subsets[yroot].min);
            }
        }
};


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    UnionSet<int> uset(arr);
    int q, type, g1, g2;
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>type;
        if (type == 1){
            cin>>g1>>g2;
            uset.unionOperation(g1, g2);
        }
        else{
            cin>>g1;
            cout<<uset.getAbsDifference(g1)<<endl;
        }
    }
}

Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){ a%=m;LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
struct dsu {
    int parent;
    int max_val;
    int min_val;
    int rank;
} s[1000001];

int find_parent(int x) {
    if(s[x].parent != x) {
        return s[x].parent = find_parent(s[x].parent);
    }
    return x;
}

void join(int x,int y) {
    int px = find_parent(x);
    int py = find_parent(y);
    if(px == py)
        return;
    if(s[px].rank < s[py].rank) {
        swap(px, py);
        swap(x, y);
    }
    s[py].parent = px;
    s[px].min_val = min(s[px].min_val, s[py].min_val);
    s[px].max_val = max(s[px].max_val, s[py].max_val);
    if(s[px].rank == s[py].rank)
        ++s[px].rank;
}


int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        s[i].parent = i;
        s[i].min_val = val;
        s[i].max_val = val;
    }
    int q;
    cin >> q;
    while(q--) {
        int query_type;
        cin >> query_type;
        if(query_type == 1) {
            int x, y;
            cin >> x >> y;
            join(x, y);
        }
        else {
            int x;
            cin >> x;
            int p = find_parent(x);
            cout << s[p].max_val - s[p].min_val << endl;
        }
    }
}

coding problems solutions