This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include <vector> #include <iostream> #include <numeric> using namespace std; #include "../../lib/00-util/FastIO.cpp" #include "../../lib/41-union-find-tree/UnionFindTree.cpp" int main(){ cin.tie(0)->sync_with_stdio(0); int N,Q; read(N); read(Q); UnionFindTree uf(N); while(Q--){ int q,a,b; read(q);read(a);read(b); if(q) cout << uf.connected(a,b) << "\n"; else uf.merge(a,b); } }
#line 1 "test/union-find-tree/UnionFindTree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/unionfind" #include <vector> #include <iostream> #include <numeric> using namespace std; #line 1 "lib/00-util/FastIO.cpp" /* * @title FastIO * @docs md/util/FastIO.md */ class FastIO{ private: inline static constexpr int ch_0='0'; inline static constexpr int ch_9='9'; inline static constexpr int ch_n='-'; inline static constexpr int ch_s=' '; inline static constexpr int ch_l='\n'; inline static void endline_skip(char& ch) { while(ch==ch_l) ch=getchar(); } template<typename T> inline static void read_integer(T &x) { int neg=0; char ch; x=0; ch=getchar(); endline_skip(ch); if(ch==ch_n) neg=1,ch=getchar(); for(;(ch_0 <= ch && ch <= ch_9); ch = getchar()) x = x*10 + (ch-ch_0); if(neg) x*=-1; } template<typename T> inline static void read_unsigned_integer(T &x) { char ch; x=0; ch=getchar(); endline_skip(ch); for(;(ch_0 <= ch && ch <= ch_9); ch = getchar()) x = x*10 + (ch-ch_0); } inline static void read_string(string &x) { char ch; x=""; ch=getchar(); endline_skip(ch); for(;(ch != ch_s && ch!=ch_l); ch = getchar()) x.push_back(ch); } inline static char ar[40]; inline static char *ch_ar; template<typename T> inline static void write_integer(T x) { ch_ar=ar; if(x< 0) putchar(ch_n), x=-x; if(x==0) putchar(ch_0); for(;x;x/=10) *ch_ar++=(ch_0+x%10); while(ch_ar--!=ar) putchar(*ch_ar); } public: inline static void read(int &x) {read_integer<int>(x);} inline static void read(long long &x) {read_integer<long long>(x);} inline static void read(unsigned int &x) {read_unsigned_integer<unsigned int>(x);} inline static void read(unsigned long long &x) {read_unsigned_integer<unsigned long long>(x);} inline static void read(string &x) {read_string(x);} inline static void read(__int128_t &x) {read_integer<__int128_t>(x);} inline static void write(__int128_t x) {write_integer<__int128_t>(x);} inline static void write(char x) {putchar(x);} }; #define read(arg) FastIO::read(arg) #define write(arg) FastIO::write(arg) #line 1 "lib/41-union-find-tree/UnionFindTree.cpp" /* * @title UnionFindTree - Union Find Tree * @docs md/union-find-tree/UnionFindTree.md */ class UnionFindTree { vector<int> parent,maxi,mini; inline int root(int n) { return (parent[n]<0?n:parent[n] = root(parent[n])); } public: UnionFindTree(const int N = 1) : parent(N,-1),maxi(N),mini(N){ iota(maxi.begin(),maxi.end(),0); iota(mini.begin(),mini.end(),0); } inline bool connected(const int n, const int m) { return root(n) == root(m); } inline void merge(int n,int m) { n = root(n); m = root(m); if (n == m) return; if(parent[n]>parent[m]) swap(n, m); parent[n] += parent[m]; parent[m] = n; maxi[n] = std::max(maxi[n],maxi[m]); mini[n] = std::min(mini[n],mini[m]); } inline int min(const int n) { return mini[root(n)]; } inline int max(const int n) { return maxi[root(n)]; } inline int size(const int n){ return (-parent[root(n)]); } inline int operator[](const int n) { return root(n); } inline void print() { for(int i = 0; i < parent.size(); ++i) cout << root(i) << " "; cout << endl; } }; #line 9 "test/union-find-tree/UnionFindTree.test.cpp" int main(){ cin.tie(0)->sync_with_stdio(0); int N,Q; read(N); read(Q); UnionFindTree uf(N); while(Q--){ int q,a,b; read(q);read(a);read(b); if(q) cout << uf.connected(a,b) << "\n"; else uf.merge(a,b); } }