This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"
#include <iostream>
#include <vector>
#include "../../../lib/data_structure/persistent_union_find.hpp"
using namespace std;
using pa = PersistentArray<int>::Node*;
int main(){
int n, q; cin >> n >> q;
PersistentUnionFind tree;
vector<pa> p(q + 1);
p[0] = tree.init(n);
int nxt = 1;
while(q--){
int t, k, u, v; cin >> t >> k >> u >> v;
k++;
if(t == 0){
p[nxt] = tree.unite(u, v, p[k]).second;
}else{
cout << (int) tree.same(u, v, p[k]) << "\n";
}
nxt++;
}
}
#line 1 "test/library_checker/data_structure/persistent_unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"
#include <iostream>
#include <vector>
#line 2 "lib/data_structure/persistent_union_find.hpp"
/**
* @brief Persistent Union Find (永続 UnionFind)
*/
#line 2 "lib/data_structure/persistent_array.hpp"
/**
* @brief Persistent Array (永続配列)
*/
#include <cstring>
template<typename T>
struct PersistentArray{
struct Node{
T data;
Node *ch[20] = {};
};
Node *root = nullptr;
PersistentArray() {}
Node *get_root(){
return root;
}
void destructive_set(const int i, const T &val, Node *&t){
if(!t) t = new Node();
if(i == 0){
t->data = val;
} else{
destructive_set(i / 20, val, t->ch[i % 20]);
}
}
Node *set(const int i, const T &val, Node *&t){
Node *res = new Node();
if(t){
std::memcpy(res->ch, t->ch, sizeof(t->ch));
res->data = t->data;
}
if(i == 0){
res->data = val;
} else{
res->ch[i % 20] = set(i / 20, val, res->ch[i % 20]);
}
return res;
}
T get(const int i, Node *t){
if(!t) return T();
if(i == 0){
return t->data;
} else{
return get(i / 20, t->ch[i % 20]);
}
}
};
#line 8 "lib/data_structure/persistent_union_find.hpp"
struct PersistentUnionFind{
PersistentArray<int> data;
using node = PersistentArray<int>::Node *;
PersistentUnionFind() {}
node init(const int n){
node res = data.get_root();
for(int i = 0; i < n; ++i){
data.destructive_set(i, -1, res);
}
return res;
}
std::pair<bool, node> unite(const int x, const int y, node t){
int rx = root(x, t), ry = root(y, t);
if(rx == ry) return {false, t};
if(data.get(ry, t) < data.get(rx, t)) std::swap(rx, ry);
node n = data.set(rx, data.get(rx, t) + data.get(ry, t), t);
node res = data.set(ry, rx, n);
return {true, res};
}
int root(const int x, node t){
if(data.get(x, t) < 0){
return x;
}
int res = root(data.get(x, t), t);
return res;
}
inline bool same(const int x, const int y, node t){
return root(x, t) == root(y, t);
}
inline int size(const int x, node t){
return -data.get(root(x, t), t);
}
};
struct PersistentUnionFindv2{
int n;
PersistentArray<int> data;
using node = PersistentArray<int>::Node *;
PersistentUnionFindv2() {}
node init(const int &_n){
n = _n;
node res = data.get_root();
for(int i = 0; i < n; ++i){
data.destructive_set(i, -1, res);
data.destructive_set(i + n, 0, res);
}
return res;
}
std::pair<bool, node> unite(const int x, const int y, node t){
int rx = root(x, t), ry = root(y, t);
if(rx == ry){
node res = data.set(rx + n, edge(rx, t) + 1, t);
return {false, res};
}
if(data.get(ry, t) < data.get(rx, t)) std::swap(rx, ry);
node res = data.set(rx, data.get(rx, t) + data.get(ry, t), t);
res = data.set(ry, rx, res);
res = data.set(rx + n, data.get(rx + n, t) + data.get(ry + n, t) + 1, res);
return {true, res};
}
int root(const int x, node t){
if(data.get(x, t) < 0){
return x;
}
int res = root(data.get(x, t), t);
return res;
}
inline bool same(const int x, const int y, node t){
return root(x, t) == root(y, t);
}
inline int size(const int x, node t){
return -data.get(root(x, t), t);
}
inline int edge(const int x, node t){
return data.get(root(x, t) + n, t);
}
};
#line 6 "test/library_checker/data_structure/persistent_unionfind.test.cpp"
using namespace std;
using pa = PersistentArray<int>::Node*;
int main(){
int n, q; cin >> n >> q;
PersistentUnionFind tree;
vector<pa> p(q + 1);
p[0] = tree.init(n);
int nxt = 1;
while(q--){
int t, k, u, v; cin >> t >> k >> u >> v;
k++;
if(t == 0){
p[nxt] = tree.unite(u, v, p[k]).second;
}else{
cout << (int) tree.same(u, v, p[k]) << "\n";
}
nxt++;
}
}