Disjoint Set Data Structure

Learn Disjoint Set Data Structure with practical examples, explanations, best practices, and real-world coding techniques.

A Disjoint Set is a data structure used to maintain a collection of non-overlapping sets. It efficiently keeps track of which elements belong to the same group and supports operations for finding an element's group and combining two separate groups.

The structure is commonly known as Disjoint Set Union (DSU) or Union-Find. It is especially useful when a program repeatedly needs to determine whether two elements belong to the same connected group and merge groups as relationships are discovered.

What Is a Disjoint Set?

A disjoint set collection contains groups where no element belongs to more than one group. For example, suppose we have the elements 1, 2, 3, 4, 5, 6. They could initially be represented as six separate sets: 


{1}  {2}  {3}  {4}  {5}  {6}

If elements 1 and 2 are connected, their sets can be combined: 


{1, 2}  {3}  {4}  {5}  {6}

Later, if 2 and 3 become connected, the first group can be merged with the group containing 3: 


{1, 2, 3}  {4}  {5}  {6}

A Disjoint Set data structure performs these grouping operations efficiently without repeatedly rebuilding the complete collection.

Disjoint Set vs Union-Find

Disjoint Set, Disjoint Set Union (DSU), and Union-Find commonly refer to the same family of data structures and algorithms.

The name Union-Find comes directly from its two primary operations: union, which combines two sets, and find, which determines the representative of the set containing an element.

Why Use a Disjoint Set?

A Disjoint Set is useful when groups continuously change because separate elements become connected. Instead of performing an expensive search through all existing relationships after every change, DSU maintains a compact representation of the groups.

This makes it particularly useful for connectivity problems, where the main question is whether two elements belong to the same component.

Core Operations of Disjoint Set

A typical Disjoint Set implementation provides three fundamental operations:

  • Make Set: Creates a new set containing an individual element.
  • Find: Determines the representative of the set containing an element.
  • Union: Combines two sets into one set.

Make Set

Initially, every element can be placed into its own independent set. Each element acts as its own representative. 


1 → 1
2 → 2
3 → 3
4 → 4

Find

The find operation identifies the representative, or root, of the set containing a particular element. Elements belonging to the same set eventually lead to the same representative.

Union

The union operation combines the sets containing two specified elements. If both elements already belong to the same set, no structural change is required.

How a Disjoint Set Is Represented

A common implementation represents each set as a tree. Every element stores a reference to its parent, and the root of the tree acts as the representative of the set. 


        1
       / \
      2   3
     /
    4

In this example, element 1 is the root and therefore represents the set. Elements 2, 3, and 4 belong to the same set because following their parent references eventually reaches 1.

Parent Array Representation

In array-based implementations, a parent array can store the parent relationship for every element. If an element is its own parent, it represents the root of its set. 


parent[1] = 1
parent[2] = 1
parent[3] = 1
parent[4] = 2

Following the parent references from 4 gives 4 → 2 → 1, so 1 is the representative of the set containing 4.

Example of Union Operations

Suppose we start with five independent sets: 


{1} {2} {3} {4} {5}

Performing union(1, 2) creates one group: 


{1, 2} {3} {4} {5}

Then union(2, 3) merges the set containing 2 with the set containing 3: 


{1, 2, 3} {4} {5}

A later union(4, 5) creates another group: 


{1, 2, 3} {4, 5}

Checking Whether Two Elements Are Connected

One of the most useful operations of DSU is checking whether two elements belong to the same set. Two elements are connected in the Disjoint Set representation when their find operations return the same representative. 


find(1) === find(3)

If both operations return the same root, the elements belong to the same connected component. Otherwise, they are currently in different sets.

Union by Rank and Path Compression

A basic Union-Find implementation can become inefficient if its trees become too tall. Two important optimizations solve this problem: union by rank and path compression.

Union by rank attaches the shorter tree below the taller tree. Path compression changes parent references during a find operation so that visited elements point much closer to the root.

These optimizations are covered in more detail in the related topics Union-Find, Path Compression, and Union by Rank.

Disjoint Set Time Complexity

With both path compression and union by rank or size, a sequence of m operations on n elements has an amortized complexity of O(m α(n)), where α(n) is the inverse Ackermann function.

The inverse Ackermann function grows extremely slowly. For practical input sizes, it behaves almost like a constant, which makes optimized Union-Find operations extremely efficient.

Operation Basic Implementation Optimized DSU
Make Set O(1) O(1)
Find Can approach O(n) Amortized O(α(n))
Union Can approach O(n) Amortized O(α(n))

Applications of Disjoint Set

Disjoint Set is useful whenever elements are gradually combined into groups and the application needs to answer connectivity questions efficiently.

  • Detecting connected components in graphs
  • Detecting cycles in undirected graphs
  • Kruskal's Minimum Spanning Tree algorithm
  • Network connectivity problems
  • Grouping related objects
  • Dynamic connectivity problems
  • Clustering and component management

Disjoint Set for Connected Components

Consider a graph where edges are added over time. Initially, every vertex can be considered an independent component. Whenever an edge connects two vertices, their sets can be merged using the union operation.

At any point, calling find for two vertices tells us whether they belong to the same connected component.

Disjoint Set and Cycle Detection

DSU can also be used to detect cycles in an undirected graph. For every edge connecting vertices u and v, first check whether find(u) and find(v) return the same representative.

If they already belong to the same set, adding the edge would connect vertices that are already connected, indicating a cycle. Otherwise, their sets can be merged using union.

Disjoint Set vs Other Data Structures

A Disjoint Set is specialized for maintaining groups that only need to be merged and queried for connectivity. It is not intended to replace general-purpose structures such as arrays, hash tables, linked lists, or search trees.

If an application needs to retrieve arbitrary values, maintain sorted order, or perform frequent insertion and deletion of individual records, another data structure may be more appropriate.

Common Disjoint Set Mistakes

  • Confusing an element with the representative of its set.
  • Calling union directly on elements without first finding their roots.
  • Forgetting path compression in performance-sensitive implementations.
  • Building unnecessarily tall trees during union operations.
  • Using DSU for problems that require more detailed graph traversal or ordering information.

Disjoint Set Example in JavaScript

The following implementation demonstrates the core Union-Find idea using a parent array. It includes path compression and union by rank so that the resulting structure remains efficient for a large sequence of operations.

Key Takeaways

  • Disjoint Set maintains a collection of non-overlapping sets.
  • It is also known as Disjoint Set Union or Union-Find.
  • The main operations are Make Set, Find, and Union.
  • Each set can be represented as a tree whose root is its representative.
  • Path compression makes Find operations faster.
  • Union by rank or size prevents unnecessarily tall trees.
  • Optimized DSU operations have near-constant amortized complexity.
  • DSU is widely used for connectivity, cycle detection, and minimum spanning tree problems.

Code Examples 


class DisjointSet {
  constructor(size) {
    this.parent = Array.from(
      { length: size },
      (_, index) => index
    );

    this.rank = new Array(size).fill(0);
  }

  find(value) {
    if (this.parent[value] !== value) {
      this.parent[value] = this.find(this.parent[value]);
    }

    return this.parent[value];
  }

  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);

    if (rootA === rootB) {
      return false;
    }

    if (this.rank[rootA] < this.rank[rootB]) {
      this.parent[rootA] = rootB;
    } else if (this.rank[rootA] > this.rank[rootB]) {
      this.parent[rootB] = rootA;
    } else {
      this.parent[rootB] = rootA;
      this.rank[rootA]++;
    }

    return true;
  }

  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

const ds = new DisjointSet(6);

ds.union(0, 1);
ds.union(1, 2);
ds.union(3, 4);

console.log(ds.connected(0, 2)); // true
console.log(ds.connected(0, 4)); // false

ds.union(2, 3);

console.log(ds.connected(0, 4)); // true

This implementation represents each set as a parent tree. Find uses path compression to shorten paths to the representative, while Union uses rank to attach the smaller tree below the larger one. 


const ds = new DisjointSet(7);

ds.union(0, 1);
ds.union(1, 2);
ds.union(3, 4);
ds.union(5, 6);

console.log(ds.connected(0, 2)); // true
console.log(ds.connected(0, 4)); // false
console.log(ds.connected(3, 5)); // false

ds.union(2, 4);

console.log(ds.connected(0, 4)); // true

This example demonstrates how separate groups can be created and progressively merged. Connectivity can be checked at any point without rebuilding the entire collection.

Pro Tip

When solving a connectivity problem, ask whether the relationships only need to be <strong>merged</strong> and queried for membership. If groups never need to split, Disjoint Set Union is often a strong fit. Remember the key test: <code>find(a) === find(b)</code> means that both elements currently belong to the same set.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.