UnionFind with counter rank

// BETA source code #include <bits/stdc++.h> using namespace std; #define vi vector<int> class UnionFind { // OOP style private: public: vi p, rank; // remember: vi is vector<int> UnionFind(int N) { rank.assign(N, 1); p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; } void unionSet(int i, int j) { if (!isSameSet(i, j)) { // if from different set int x = findSet(i), y = findSet(j); if (rank[x] > rank[y]) swap(x,y); // y must be bigger than of x p[x] = y; rank[y]+=rank[x]; } } int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); } bool isSameSet(int i, int j) { return findSet(i) == findSet(j); } }; int main() { int n = 10; UnionFind u(n); u.unionSet(0,1); u.unionSet(1,2); u.unionSet(0,1); u.unionSet(0,1); for (int i=0 ; i<n ; i++) if (i==u.p[i]) cout<<i<<"("<<u.rank[i]<<") "; cout<<"\n"; u.unionSet(8,9); u.unionSet(8,0); u.unionSet(6,7); u.unionSet(6,5); for (int i=0 ; i<n ; i++) if (i==u.p[i]) cout<<i<<"("<<u.rank[i]<<") "; cout<<"\n"; return 0; }