Path Compression And Union by Size

A combination of two optimization techniques for Disjoint Set Union (DSU)

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?

1

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.
2

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.
3

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.
Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6

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);
}

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?

1

The root of the smaller-sized tree becomes a child of the root of the larger-sized tree to keep the tree balanced.

2

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]++;
}
}

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 << " ";
}
}