> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/union-find-dynamic-connectivity-problem/implementation.md).

# Implementation

Documentation: [click here!](https://prydt.github.io/algorithms/union_find/union_find)

## Weighted Quick-Union with Path Compression (WQUPC)

```cpp
#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();
}
```

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2F6wXCJyBNnpBM0ueXm6PN%2Fimage.png?alt=media&amp;token=82dc3d5c-4683-4182-b940-1942b40e179f" alt=""><figcaption></figcaption></figure>

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2F6usB3PfKLNZbtUhjcn7O%2Fimage.png?alt=media&amp;token=bd835c38-44a3-4fd4-9ee7-bcf5fa9a1ccb" alt=""><figcaption></figcaption></figure>