# 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:

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

## 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.00000001LL 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;        }    }}`