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.
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;
}
}
}