Path Compression And Union by Size

Path Compression

When finding the root of a set, instead of just returning the root we make every node on the path point directly to the root. This drastically reduces the tree's height, making future operations faster.

How Path Compression Works?

Base Case

If x == parent[x], this means that the element x is the root of its set. Therefore, x is returned as the result.

Recursive Case

If x is not the root, the function recursively finds the parent of x by calling find() on parent[x]. This continues until it reaches the root.

Path Compression

parent[x] = find(parent[x], parent) performs path compression. It directly links x to its root, which helps speed up future queries by flattening the structure of the tree.

Implementation: Path Compression

//pathCompression.cpp
int find(int x, vector<int> &parent)
{
if (x == parent[x])
    return x;
return parent[x] = find(parent[x], parent);
}

print("We're Working")

console.log("We're Working");

Union by Size is another optimization technique used in the Union-Find (DSU) data structure to keep the tree as flat as possible. Instead of using rank, it considers the size (number of nodes) of each set when performing a union operation.

Difference from Union by Rank

Union by Rank focuses on tree height (rank).
Union by Size focuses on the number of elements in each tree.

How Union By Size Works?

The root of the smaller-sized tree becomes a child of the root of the larger-sized tree to keep the tree balanced.
If both sets have the same size either can become the root and the size of the new root is updated accordingly.

Implementation: Union By Size

//unionbySize.cpp
void Union(int a, int b, vector<int> &parent,vector<int> &size)
{
int a_parent = find(a, parent);
int b_parent = find(b, parent);
if (a_parent == b_parent)
{
    return;
}
else if (size[a_parent] > size[b_parent])
{
    parent[b_parent] = a_parent;
    size[a_parent]+=size[b_parent];
}
else if (size[b_parent] > size[a_parent])
{
    parent[a_parent] = b_parent;
    size[b_parent]+=size[a_parent];
}
else{
    parent[b_parent]=a_parent;
    size[a_parent]++;
}
}

print("We're Working")

console.log("We're Working");

Implementation of DSU (Path Compression and Union By Size)

//dsubypathcompressionandunionbysize.cpp
#include<iostream>
#include <vector>
using namespace std;
int find(int x, vector<int> &parent)
{
if (x == parent[x])
    return x;
return parent[x] = find(parent[x], parent);
}
void Union(int a, int b, vector<int> &parent,vector<int> &size)
{
int a_parent = find(a, parent);
int b_parent = find(b, parent);
if (a_parent == b_parent)
{
    return;
}
else if (size[a_parent] > size[b_parent])
{
    parent[b_parent] = a_parent;
    size[a_parent]+=size[b_parent];
}
else if (size[b_parent] > size[a_parent])
{
    parent[a_parent] = b_parent;
    size[b_parent]+=size[a_parent];
}
else{
    parent[b_parent]=a_parent;
    size[a_parent]++;
}
}
int main()
{
int n;
cin >> n;
vector<int> parent(n);
vector<int> size(n,1);
for (int i = 0; i < n; i++)
{
    parent[i] = i;
}
Union(0, 1, parent,size);
Union(3, 4, parent,size);
Union(0, 3, parent,size);
for (int i = 0; i < n; i++) {
    find(i, parent);
}
for (int &ele : parent)
{
    cout << ele << " ";
}
}

print("We're Working")

console.log("We're Working");

Path Compression And Union by Size

On this page