This documentation is automatically generated by online-judge-tools/verification-helper
#include "DataStructure/persistentunionfind.hpp"
#pragma once
#include "DataStructure/persistentarray.hpp"
struct PersistentUnionFind{
PersistentArray<int> dat;
PersistentUnionFind(int n){
rep(i,0,n)dat.set(i,-1);
}
int root(int x){
if(dat.get(x)<0)return x;
else return root(dat.get(x));
}
bool unite(int x,int y){
x=root(x),y=root(y);
if(x==y)return false;
int p=dat.get(x),q=dat.get(y);
if(p>q)swap(x,y);
dat.set(x,p+q);
dat.set(y,x);
return true;
}
bool same(int x,int y){return root(x)==root(y);}
int size(int a){return -dat.get(root(a));}
};
/**
* @brief Persistent Union Find
*/
#line 2 "DataStructure/persistentarray.hpp"
template<typename T,int B=4>class PersistentArray{
const int M=(1<<B)-1;
struct Node{
Node *cp[1<<B]={};
T val;
};
Node* set(int i,T x,Node* a){
Node *ret=new Node();
if(a){
memcpy(ret->cp,a->cp,sizeof(a->cp));
ret->val=a->val;
}
if(i)ret->cp[i&M]=set(i>>B,x,ret->cp[i&M]);
else ret->val=x;
return ret;
}
T get(int i,Node* a){
if(i)return get(i>>B,a->cp[i&M]);
else return a->val;
}
public:
Node *root;
PersistentArray(Node* _r=nullptr):root(_r){}
void set(int i,T x){
root=set(i,x,root);
}
T get(int i){
return get(i,root);
}
};
/**
* @brief Persistent Array
*/
#line 3 "DataStructure/persistentunionfind.hpp"
struct PersistentUnionFind{
PersistentArray<int> dat;
PersistentUnionFind(int n){
rep(i,0,n)dat.set(i,-1);
}
int root(int x){
if(dat.get(x)<0)return x;
else return root(dat.get(x));
}
bool unite(int x,int y){
x=root(x),y=root(y);
if(x==y)return false;
int p=dat.get(x),q=dat.get(y);
if(p>q)swap(x,y);
dat.set(x,p+q);
dat.set(y,x);
return true;
}
bool same(int x,int y){return root(x)==root(y);}
int size(int a){return -dat.get(root(a));}
};
/**
* @brief Persistent Union Find
*/