Disjoint Set (Union-Find) with Union by Rank, Size and Path Compression

Problem Statement❯

The Disjoint Set (also called Union-Find) is a data structure used to manage a collection of non-overlapping sets. It supports two main operations:

Find: Determine which set a particular element belongs to.
Union: Merge two sets into a single set.

Disjoint Set is particularly useful in problems involving connected components, cycle detection in graphs, and Kruskal's algorithm for Minimum Spanning Tree.

To improve efficiency, it uses two optimizations:

Union by Rank or Union by Size: Always attach the smaller tree under the root of the larger tree.
Path Compression: Flatten the tree whenever Find is used, making future queries faster.

Examples❯

Operation	Effect	Description
find(3)	Returns the representative of the set containing 3	If 3 is part of the set with root 1, find(3) returns 1
union(1, 2)	Merges the sets containing 1 and 2	Uses rank/size to decide which root becomes the parent
find(3) after path compression	Directly points to root	Improves future queries by reducing depth
union(1, 3)	May not change structure if both already connected	No change if already in same set

Solution❯

The Disjoint Set data structure efficiently handles union and find operations on dynamic partitions of a set. Initially, each element is its own parent, forming a singleton set. The goal is to repeatedly merge sets and answer queries about element connectivity or group membership.

Union by Rank/Size: When merging two sets, we attach the root of the smaller set (by height or size) to the root of the larger set. This avoids increasing the height of the tree unnecessarily, leading to faster find operations.

Path Compression: During the Find operation, we recursively make every node on the path point directly to the root. This flattens the structure of the tree and drastically reduces the time complexity of future Find operations.

These optimizations together reduce the time complexity of each operation nearly to O(α(n)), where α is the inverse Ackermann function, which grows extremely slowly — effectively constant for practical input sizes.

Use cases include Kruskal’s MST algorithm, checking if two elements are in the same connected component, detecting cycles in undirected graphs, and network connectivity problems.

Algorithm Steps❯

Initialization: Set each node as its own parent and rank/size as 1.
Find(x):
1. If x is not the parent of itself, recursively call Find on its parent.
2. Apply path compression by setting the parent of x to the result of Find.
Union(x, y):
1. Find roots of both x and y.
2. If they are the same, no union is needed (already connected).
3. Else, attach the smaller rank/size tree under the larger one.
4. If ranks are equal, arbitrarily choose one and increment its rank.

Code

JavaScript

class DisjointSet {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // Path Compression
    }
    return this.parent[x];
  }

  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);

    if (rootX === rootY) return;

    // Union by Rank
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
  }
}

const ds = new DisjointSet(5);
ds.union(0, 1);
ds.union(1, 2);
console.log("Find(2):", ds.find(2)); // Should be 0
console.log("Find(3):", ds.find(3)); // Should be 3 (not connected)

⬅ Previous TopicPrim's Algorithm for Minimum Spanning Tree

Next Topic ⮕Kruskal's Algorithm - Minimum Spanning Tree