fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <functional>
  7. #include <utility>
  8. #define pb push_back
  9. #define mp make_pair
  10. #define ft first
  11. #define nd second
  12. #define init(x,n,y) x.assign(n,y);
  13. #define Kagami(f) f.end()
  14. #define Natsu(f) f.begin()
  15. #define NatsuKagami(f) f.begin(),f.end()
  16. #define low(f,x) lower_bound(f.begin(),f.end(),x) 
  17. #define hi(f,x) upper_bound(f.begin(),f.end(),x)
  18. #define poi(a,x,y) for(int a = x; a < y; ++a)
  19. #define meow(a,x,y) for (int a = x; a >= y; --a)
  20. using namespace std;
  21.  
  22. typedef vector<int> vi;
  23. int n,m;
  24. int q, t, u, v;
  25.  
  26. vi dsu; int setCount;
  27. int find(int i) {return dsu[i]<0?i:dsu[i]=find(dsu[i]);}
  28. bool same(int i, int j) {return find(i)==find(j);}
  29. void join(int i, int j) {
  30. 	if (same(i,j)) return; --setCount, i = find(i), j = find(j);
  31. 	if (dsu[i]>dsu[j]) swap(i,j);
  32. 	dsu[i]+=dsu[j]; dsu[j]=i;
  33. }
  34. void initDsu(int size) {
  35. 	setCount = size; init(dsu,size,-1);
  36. }
  37.  
  38. int main() {
  39. 	ios_base::sync_with_stdio(false);
  40. 	freopen("no112b.inp","r",stdin);
  41. 	freopen("no112b.out","w",stdout);
  42. 	scanf("%d",&n); initDsu(n+1);
  43. 	scanf("%d",&m); while (m--) {scanf("%d%d",&u,&v); join(u,v);}
  44. 	scanf("%d",&q);
  45. 	while (q--) {
  46. 		scanf("%d%d%d",&t,&u,&v);
  47. 		if (t==1) printf("%d",(same(u,v)?1:0));
  48. 		else join(u,v);
  49. 	}
  50. 	printf("\n"); 
  51. }
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JWWxfL
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!