Implementation

Documentation: click here!

Weighted Quick-Union with Path Compression (WQUPC)

#include <iostream>
using namespace std;

class QuickUnionUF {
     int *id;
     int *size;
     int n;

     int root(int i) {
          while (i != id[i]) {
               id[i] = id[id[i]]; // Path Compression (Keeps tree almost completely flat) Improvement. only one extra line of code 
               i = id[i];
          }
          return i;
     }

public:
     QuickUnionUF(int n) : n(n) {
          id = new int[n];
          size = new int[n];
          for (int i = 0; i < n; i++) {
               id[i] = i;
               size[i] = 1;
          }
     }

     bool Connected(int p, int q) {
          return root(p) == root(q);
     }

     void Union(int p, int q) {
          int rootA = root(p);
          int rootB= root(q);
          
          if (rootA == rootB) return;

          if (size[rootA] < size[rootB]) {
               id[rootA] = rootB;
               size[rootB] += size[rootA];
          }
          else {
               id[rootB] = rootA;
               size[rootA] += size[rootB];
          }
     }

     void print() {
          for (int i = 0; i < n; i++)
               cout << id[i] << " ";
     }
};

int main()
{
     int n;
     cout << "Enter Size: ";
     cin >> n;

     QuickUnionUF *obj = new QuickUnionUF(n);
     while (1) {
          int p, q;
          cin >> p >> q;
          if (p < 0 || q >= n || q < 0 || q >= n) break;
          
          if (!obj->Connected(p, q))
          {
               obj->Union(p, q);
               cout << p << " " << q << endl;
          }
          else cout << "Already Connected!" << endl;
          
     }
     obj->print();
}