Union-Find Data Structure Explained

Learn Union-Find Data Structure Explained with practical examples, explanations, best practices, and real-world coding techniques.

What Is Union-Find?

Union-Find is a data structure used to keep track of a collection of disjoint sets. It efficiently determines whether two elements belong to the same group and can merge two groups into one.

It is also commonly called the Disjoint Set Union (DSU) data structure. The two fundamental operations are Find, which identifies the representative of a set, and Union, which combines two sets.

Why Do We Need Union-Find?

Consider a network where computers are connected to each other. You may need to answer questions such as whether two computers are connected or whether connecting two computers would create a cycle.

A Union-Find structure can answer these connectivity questions without repeatedly traversing the entire network.

  • Check whether two elements belong to the same set.
  • Merge two previously separate sets.
  • Track connected components in an undirected graph.
  • Detect cycles while processing graph edges.
  • Support algorithms such as Kruskal's minimum spanning tree algorithm.

The Core Idea

Union-Find represents every set as a tree. Each element stores a reference to its parent, and the root of the tree acts as the representative of the entire set.

For example, suppose we have:

0   1   2   3   4

Each element initially belongs to its own set.

{0} {1} {2} {3} {4}

If we perform union(0, 1), the two sets become one: 

{0, 1} {2} {3} {4}

After another operation such as union(1, 2), the first set becomes: 

{0, 1, 2} {3} {4}

The important point is that Union-Find does not need to store every set as a separate collection. It uses parent relationships to represent the groups.

Find Operation

The Find operation determines the representative, or root, of the set containing a given element.

If an element is its own parent, it is the root of the set. Otherwise, we continue following parent references until the root is reached. 

    0
    |
    1
    |
    2

parent[2] = 1
parent[1] = 0
parent[0] = 0

find(2) → 0

Here, 0 is the representative of the set containing 0, 1, and 2.

Union Operation

The Union operation combines two sets. Before joining them, Union-Find first finds the root of each element.

If both elements already have the same root, they are already part of the same set. Otherwise, one root is connected to the other root. 

Set A: {0, 1}
Set B: {2, 3}

union(1, 2)

Result: {0, 1, 2, 3}

Parent Array Representation

A common Union-Find implementation uses an array called parent. Each index represents an element, while the value at that index identifies its parent. 

parent = [0, 0, 1, 3, 3]

Element:  0  1  2  3  4
Parent:   0  0  1  3  3

In this example, 0 is the root of the set containing 0, 1, 2, while 3 is the root of the set containing 3, 4.

Creating the Initial Sets

Initially, every element forms its own independent set. Therefore, every element is its own parent. 

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

This represents five separate sets: 

{0}
{1}
{2}
{3}
{4}

Union-Find With JavaScript

The following implementation demonstrates the basic Union-Find structure using a parent array. It supports creating sets, finding representatives, and merging sets.

Checking Whether Two Elements Are Connected

Two elements belong to the same set when their representatives are equal. Therefore, connectivity can be checked by comparing the results of two find operations. 

find(a) === find(b)

This simple comparison is one of the main reasons Union-Find is useful for connectivity problems.

Union-Find and Connected Components

In an undirected graph, a connected component is a group of vertices where every vertex can be reached from the others through one or more edges.

Union-Find can build these components while edges are processed. For every edge (u, v), perform a union between u and v. Vertices that eventually have the same representative belong to the same connected component.

Using Union-Find for Cycle Detection

Union-Find can detect cycles in an undirected graph while processing edges. For each edge (u, v), find the representatives of both vertices.

  • If the representatives are different, the edge connects two separate components.
  • If the representatives are already equal, the two vertices are already connected.
  • Adding that edge would create a cycle.
Edge (0, 1)
0 and 1 are separate → union

Edge (1, 2)
1 and 2 are separate → union

Edge (0, 2)
0 and 2 have the same root → cycle detected

Union-Find in Kruskal's Algorithm

Union-Find is an important component of Kruskal's algorithm for finding a minimum spanning tree.

Kruskal's algorithm processes graph edges in increasing order of weight. Before adding an edge, it checks whether the two endpoints already belong to the same component.

  • If they belong to different sets, the edge can be added.
  • The two sets are then merged using Union-Find.
  • If they belong to the same set, adding the edge would create a cycle.

This makes Union-Find particularly useful when a graph algorithm repeatedly needs to merge components and test whether vertices are already connected.

Path Compression

A basic Union-Find implementation can produce tall trees. Searching for a root in a tall tree can require following many parent references.

Path compression improves future operations by making nodes point directly to the root after a find operation. 

Before:

    0
    |
    1
    |
    2
    |
    3

After find(3):

    0
   /|\
  1 2 3

Path compression is an optimization of Union-Find and is usually combined with another technique called union by rank or union by size.

Union by Rank

Union by rank keeps Union-Find trees relatively shallow by attaching the root of the smaller-ranked tree to the root of the larger-ranked tree.

The rank generally represents an estimate of the tree's height. Keeping trees shallow makes future find operations more efficient.

Time Complexity

The efficiency of Union-Find depends heavily on the optimizations used.

Operation Basic Implementation Path Compression + Union by Rank
Find O(n) worst case Amortized O(α(n))
Union Depends on Find Amortized O(α(n))

Here, α(n) is the inverse Ackermann function. It grows so slowly that for practical input sizes it behaves almost like a constant.

Union-Find vs Other Graph Traversal Techniques

Union-Find and graph traversal algorithms such as BFS and DFS can both be used when working with connectivity, but they solve the problem differently.

  • Union-Find: efficient when components are repeatedly merged and connectivity is queried.
  • BFS: useful for exploring vertices level by level.
  • DFS: useful for traversal, component exploration, and many graph algorithms.

Union-Find is especially useful when the graph is being processed as a sequence of connections rather than explored through adjacency relationships.

Common Applications of Union-Find

  • Connected component detection
  • Cycle detection in undirected graphs
  • Kruskal's minimum spanning tree algorithm
  • Network connectivity problems
  • Grouping and clustering operations
  • Dynamic connectivity problems
  • Percolation and grid connectivity problems

When Should You Use Union-Find?

Union-Find is a strong choice when your problem repeatedly performs two operations: merge two groups and check whether two elements belong to the same group.

It is less suitable when you need detailed information about paths, distances, ordering, or the actual route between vertices. In those cases, graph traversal or shortest-path algorithms may be more appropriate.

Key Takeaways

  • Union-Find manages a collection of disjoint sets.
  • The Find operation identifies the representative of a set.
  • The Union operation merges two different sets.
  • A parent array is commonly used to represent the structure.
  • Union-Find can efficiently answer connectivity queries.
  • It can detect cycles in undirected graphs.
  • Kruskal's algorithm uses Union-Find to avoid creating cycles.
  • Path compression and union by rank significantly improve performance.
  • The optimized structure provides nearly constant amortized operation time.

Code Examples 

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

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

    return this.parent[x];
  }

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

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

    this.parent[rootB] = rootA;
    return true;
  }

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

const uf = new UnionFind(5);

uf.union(0, 1);
uf.union(1, 2);

console.log(uf.connected(0, 2)); // true
console.log(uf.connected(0, 3)); // false
    
function hasCycle(edges, vertices) {
  const uf = new UnionFind(vertices);

  for (const [u, v] of edges) {
    if (!uf.union(u, v)) {
      return true;
    }
  }

  return false;
}

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

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

    return this.parent[x];
  }

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

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

    this.parent[rootB] = rootA;
    return true;
  }
}

const edges = [
  [0, 1],
  [1, 2],
  [0, 2]
];

console.log(hasCycle(edges, 3)); // true

Pro Tip

When implementing Union-Find for real problems, combine path compression with union by rank or union by size. Using both optimizations keeps the trees shallow and makes repeated connectivity operations extremely efficient.

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