Union-Find: A Simple Guide

What is Union-Find?

If you’re diving into algorithms or data structures, you’ll bump into the Union-Find (also known as Disjoint-Set Union or DSU) data structure. It’s not the most glamorous topic, but it’s incredibly useful for solving certain problems efficiently. Think of it as a way to keep track of a collection of items that can be grouped together.

At its core, Union-Find manages a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It supports two primary operations:

1. find(i): Determine which subset an element i belongs to. This operation returns a representative (or “leader”) of the set that i is in.
2. union(i, j): Merge the two subsets containing elements i and j into a single subset.

Why Use It?

Union-Find shines when you need to answer questions like “Are these two items connected?” or “How many separate groups are there?”. Common use cases include:

• Kruskal’s Algorithm: For finding the Minimum Spanning Tree (MST) of a graph. You use Union-Find to ensure you don’t create cycles when adding edges.
• Detecting Cycles in Graphs: Similar to Kruskal’s, if you try to union two nodes that are already in the same set, you’ve found a cycle.
• Connected Components: Finding groups of connected nodes in a graph.
• Image Processing: Segmenting regions in an image.

How it Works: The Basic Idea

The most straightforward way to implement Union-Find is using an array where each index represents an element. We can think of this array as representing a forest of trees, where each tree is a subset. The root of each tree is the representative of that subset.

We’ll use an array, let’s call it parent, where parent[i] stores the parent of element i. If parent[i] == i, then i is the root of its tree (and thus the representative of its set).

The find Operation

To find the representative of an element i, we just traverse up the tree by following the parent pointers until we reach the root (an element whose parent is itself).

1
function find(parent, i) {
2
  if (parent[i] === i) {
3
    return i;
4
  }
5
  return find(parent, parent[i]);
6
}

The union Operation

To union two sets containing elements i and j, we first find their respective representatives, say rootI and rootJ. If rootI and rootJ are different, it means i and j are in different sets. We then make one root the parent of the other, effectively merging the trees.

1
function union(parent, i, j) {
2
  const rootI = find(parent, i);
3
  const rootJ = find(parent, j);
4

5
  if (rootI !== rootJ) {
6
    parent[rootI] = rootJ; // Make rootJ the parent of rootI
7
  }
8
}

Initialization

Initially, each element is in its own set. So, for n elements, we initialize the parent array such that parent[i] = i for all i from 0 to n-1.

1
function initialize(n) {
2
  const parent = new Array(n);
3
  for (let i = 0; i < n; i++) {
4
    parent[i] = i;
5
  }
6
  return parent;
7
}

Optimizations: Path Compression and Union by Rank/Size

The basic implementation can be slow if the trees become very tall and skinny (like a linked list). To make it efficient, we use two optimizations:

1. Path Compression: When we call find(i), after finding the root, we make every node on the path from i to the root point directly to the root. This flattens the tree.

   1
   function find(parent, i) {
   2
     if (parent[i] === i) {
   3
       return i;
   4
     }
   5
     // Path compression
   6
     parent[i] = find(parent, parent[i]);
   7
     return parent[i];
   8
   }

2. Union by Rank (or Size): When merging two trees, we attach the shorter tree to the root of the taller tree. This helps keep the trees balanced. We can track the “rank” (an approximation of height) or “size” (number of nodes) of each tree. If ranks/sizes are equal, pick one and increment its rank/size.

   For simplicity, let’s use size.

   1
   // Need a size array, initialized to 1 for each element
   2
   // let size = new Array(n).fill(1);
   3
   
   4
   function union(parent, size, i, j) {
   5
     const rootI = find(parent, i);
   6
     const rootJ = find(parent, j);
   7
   
   8
     if (rootI !== rootJ) {
   9
       if (size[rootI] < size[rootJ]) {
   10
         parent[rootI] = rootJ;
   11
         size[rootJ] += size[rootI];
   12
       } else {
   13
         parent[rootJ] = rootI;
   14
         size[rootI] += size[rootJ];
   15
       }
   16
     }
   17
   }

With these optimizations, the amortized time complexity for both find and union operations becomes nearly constant, specifically O(α(n)), where α is the inverse Ackermann function. This function grows incredibly slowly, so for all practical purposes, it’s considered constant.

Putting It All Together (Optimized)

Here’s a class encapsulating the optimized Union-Find structure.

1
class UnionFind {
2
  constructor(n) {
3
    this.parent = Array(n).fill(0).map((_, i) => i);
4
    this.size = Array(n).fill(1);
5
    this.count = n; // Number of disjoint sets
6
  }
7

8
  find(i) {
9
    if (this.parent[i] === i) {
10
      return i;
11
    }
12
    // Path compression
13
    this.parent[i] = this.find(this.parent[i]);
14
    return this.parent[i];
15
  }
16

17
  union(i, j) {
18
    const rootI = this.find(i);
19
    const rootJ = this.find(j);
20

21
    if (rootI !== rootJ) {
22
      // Union by size
23
      if (this.size[rootI] < this.size[rootJ]) {
24
        this.parent[rootI] = rootJ;
25
        this.size[rootJ] += this.size[rootI];
26
      } else {
27
        this.parent[rootJ] = rootI;
28
        this.size[rootI] += this.size[rootJ];
29
      }
30
      this.count--;
31
      return true; // Union occurred
32
    }
33
    return false; // Already in the same set
34
  }
35

36
  connected(i, j) {
37
    return this.find(i) === this.find(j);
38
  }
39

40
  getSetCount() {
41
    return this.count;
42
  }
43
}
44

45
// Example Usage:
46
// const uf = new UnionFind(10);
47
// uf.union(1, 2);
48
// uf.union(3, 4);
49
// uf.union(1, 4);
50
// console.log(uf.connected(2, 3)); // true
51
// console.log(uf.getSetCount()); // 7

Conclusion

The Union-Find data structure is a powerful tool for managing disjoint sets. While the basic concept is simple, the optimizations like path compression and union by rank/size make it remarkably efficient. Understanding and implementing Union-Find will definitely help you tackle a variety of algorithmic challenges.