fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Dsu {
  5.  
  6. public:
  7.     Dsu(int n) : rank(n+1, 1), parent(n+1, 0) {
  8.     	for (int i = 0; i < parent.size(); ++i) {
  9.     		parent[i] = i;
  10.     	}
  11.     }
  12.  
  13.     void unionByRank(int a, int b) {
  14.     	int parA = find(a);
  15.     	int parB = find(b);
  16.  
  17.     	if (rank[parA] > rank[parB]) {
  18.     		parent[parB] = parA;
  19.     		rank[parA] += rank[parB];
  20.     	} else {
  21.     		parent[parA] = parB;
  22.     		rank[parB] += rank[parA];
  23.     	}
  24.     }
  25.  
  26.     int find(int x) {
  27.     	if (parent[x] == x) {
  28.     		return x;
  29.     	}
  30.     	return parent[x] = find(parent[x]);
  31.     }
  32.  
  33.     int numConnections(int x) { return rank[find(x)]; }
  34.  
  35.     string areConnected(int x, int y) {
  36.     	return find(x) == find(y) ? "Yes" : "No";
  37.     }
  38.  
  39. private:
  40.     vector<int> rank;
  41.     vector<int> parent;
  42. };
  43.  
  44.  
  45. int main() {
  46.  
  47. 	Dsu dsu(7);
  48. 	dsu.unionByRank(1, 2);
  49. 	dsu.unionByRank(3, 4);
  50. 	dsu.unionByRank(5, 6);
  51. 	dsu.unionByRank(2, 3);
  52.  
  53.  
  54. 	cout << "People in group 1: " << dsu.numConnections(1) << endl;
  55. 	cout << "People in group 5: " << dsu.numConnections(5) << endl;
  56. 	cout << "People in group 7: " << dsu.numConnections(7) << endl;
  57.  
  58. 	cout << "Are 2 and 4 connected: " << dsu.areConnected(2, 4) << endl;
  59. 	cout << "Are 7 and 4 connected: " << dsu.areConnected(4, 7) << endl;
  60.  
  61. 	return 0;
  62. }
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
People in group 1: 4
People in group 5: 2
People in group 7: 1
Are 2 and 4 connected: Yes
Are 7 and 4 connected: No
https://ideone.com/T9CGOy
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!