This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include "head.hpp"
#include "data_structure/DSU.hpp"
#include "io/Scanner.hpp"
#include "io/Printer.hpp"
Scanner scanner;
Printer printer;
int main()
{
#ifdef ONLINE_JUDGE
ioclear;
#endif
int n, q;
scanner.scan(n, q);
DSU<int> dsu(n + 10);
for(int i = 1;i <= q;i++)
{
int t, u, v;
scanner.scan(t, u, v);
if(t == 0)
dsu.merge(u, v);
else
printer.print(dsu.same(u, v)), printer.putchar('\n');
}
}#line 1 "test/library_checker/DSU.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#line 1 "head.hpp"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'
#define CLOCK 1e3 * clock() / CLOCKS_PER_SEC
#line 2 "data_structure/DSU.hpp"
template<typename T>
struct DSU
{
std::vector<T> f, siz;
DSU() {}
DSU(int n) {init(n);}
void init(int n)
{
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
T find(T x)
{
while(x != f[x])
x = f[x] = f[f[x]];
return x;
}
bool same(T x, T y) {return find(x) == find(y);}
bool merge(T x, T y)
{
x = find(x);
y = find(y);
if(x == y)
return false;
siz[x] += siz[y];
f[y] = x;
return true;
}
T size(T x) {return siz[find(x)];}
};
#line 2 "io/Scanner.hpp"
class Scanner
{
public:
Scanner(std::FILE *f = stdin, std::size_t enough_buffer_size = 1 << 25)
: f_(f), buffer_(new char[enough_buffer_size + 32]), buffer_head_(buffer_),
buffer_tail_(buffer_ + std::fread(buffer_, sizeof(char), enough_buffer_size + 32, f_)) {*buffer_tail_ = '\0';}
~Scanner() {delete[] buffer_;}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, bool>
scan(T &x)
{
x = 0;
while(*buffer_head_ != '-' && std::isspace(*buffer_head_))
++buffer_head_;
bool is_neg = *buffer_head_ == '-' && ++buffer_head_;
char *old_buffer_head = buffer_head_;
if(is_neg)
while(std::isdigit(*buffer_head_)) x = x * 10 - (*buffer_head_++ - '0');
else
while(std::isdigit(*buffer_head_)) x = x * 10 + (*buffer_head_++ - '0');
return buffer_head_ != old_buffer_head;
}
template<typename... T>
bool scan(T &...x)
{
return (... && scan(x));
}
private:
std::FILE *f_;
char *buffer_, *buffer_head_, *buffer_tail_;
};
#line 2 "io/Printer.hpp"
class Printer
{
public:
Printer(std::FILE *f = stdout, std::size_t buffer_size = 100000)
: f_(f), buffer_(new char[buffer_size + 32]), buffer_head_(buffer_),
buffer_end_(buffer_ + buffer_size + 32), stk_(new char[32]), top_(stk_) {}
~Printer()
{
flush();
delete[] stk_;
delete[] buffer_;
}
void flush()
{
std::fwrite(buffer_, buffer_head_ - buffer_, sizeof(char), f_);
buffer_head_ = buffer_;
}
void putchar(char x)
{
if(buffer_end_ == buffer_head_)
flush();
*buffer_head_++ = x;
}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, void>
print(T x)
{
if(x == 0)
return this->putchar('0');
if(x < 0)
{
putchar('-');
do
{
T y = x / 10;
*top_++ = y * 10 - x + '0';
x = y;
} while(x != 0);
}
else
{
do
{
T y = x / 10;
*top_++ = x - y * 10 + '0';
x = y;
} while(x != 0);
}
if(buffer_end_ - buffer_head_ < top_ - stk_)
flush();
while(top_ != stk_) *buffer_head_++ = *--top_;
}
void print(char x) {return this->putchar(x);}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_unsigned_v<T>, void>
print(T x)
{
if(x == 0)
return this->putchar('0');
do
{
T y = x / 10;
*top_++ = x - y * 10 + '0';
x = y;
} while(x != 0);
if(buffer_end_ - buffer_head_ < top_ - stk_)
flush();
while(top_ != stk_) *buffer_head_++ = *--top_;
}
template<typename... T>
void print(T... x)
{
return (..., print(x));
}
template<typename T>
void println(T x)
{
return this->print(x), this->putchar('\n');
}
private:
std::FILE *f_;
char *buffer_, *buffer_head_, *buffer_end_, *stk_, *top_;
};
#line 6 "test/library_checker/DSU.test.cpp"
Scanner scanner;
Printer printer;
int main()
{
#ifdef ONLINE_JUDGE
ioclear;
#endif
int n, q;
scanner.scan(n, q);
DSU<int> dsu(n + 10);
for(int i = 1;i <= q;i++)
{
int t, u, v;
scanner.scan(t, u, v);
if(t == 0)
dsu.merge(u, v);
else
printer.print(dsu.same(u, v)), printer.putchar('\n');
}
}