fork download 
  1. #include<bits/stdc++.h>
  2. #define MAX   100100
  3. #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
  4. #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
  5. using namespace std;
  6. class DisjointSet {
  7. 	private:
  8. 	vector<int> label; //label[x] stores the root of x if x is not root, otherwise it stores -(size of x's set).
  9. 	public:
  10. 	DisjointSet(){}
  11. 	DisjointSet(int n) {
  12. 		label.assign(n+7,-1); //label should contains at least n+1 elements, as x is 1-indexed.
  13. 		//At first, each node is a seperate set of size 1.		
  14. 	}
  15. 	int find(int x) { //find the root of set which contains x.
  16. 		if (label[x]<0) return (x); //x is root iff label[x] is negative.
  17. 		label[x]=find(label[x]);
  18. 		return (label[x]); //find the root of x by recursion.
  19. 	}
  20. 	bool join(int a,int b) { // join the sets which contains a and b. Return false iff a and b are already in the same set.
  21. 		int x=find(a);
  22. 		int y=find(b);
  23. 		if (x==y) return (false); //A set contains both a and b.
  24. 		if (label[x]>label[y]) swap(x,y); //label[x]>label[y] means size(x)<size(y).
  25. 		//We speed up the disjoint set by joinning the smaller set to the bigger set		
  26. 		label[x]+=label[y];
  27. 		label[y]=x; //Update the label of x and y.		
  28. 		return (true);
  29. 	}
  30. 	int getSize(int x) { //return the size of set which contains x.
  31. 		return (-label[find(x)]);
  32. 	}
  33. };
  34. //This code is used to solve the problem: http://v...content-available-to-author-only...j.com/problems/IOIBIN/
  35. int main(void) {
  36. 	DisjointSet dsu(MAX);
  37. 	int q;
  38. 	scanf("%d",&q);
  39. 	REP(zz,q) {
  40. 		int u,v,t;
  41. 		scanf("%d%d%d",&u,&v,&t);
  42. 		if (t==1) dsu.join(u,v); else printf("%d\n",dsu.find(u)==dsu.find(v));
  43. 	}
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 3348KB
comments (?)
stdin 
9
1 2 2 
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2
stdout 
0
0
1
0
1
0
https://ideone.com/Z9s4nh
language:
C++ (gcc 8.3)
created:
10 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!