Disjoint-Set Data Structure

The Disjoint-Set Data Structure, also known as Union-Find, is used for keeping track of a set of elements partitioned into disjoint (non-overlapping) subsets. It supports two operations:

  1. Union: Join two subsets into a single subset.
  2. Find: Determine which subset an element belongs to.

Algorithm

  1. Initialization: Initialize parent array. For each element, the parent is itself.
  2. Union: Merge two subsets by changing the parent of the root of one set to the root of the other.
  3. Find: Locate the root of a set for a given element. Update the parent pointers along the path.

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class DisjointSet {
  private int[] parent;
  
  public DisjointSet(int size) {
    parent = new int[size];
    for (int i = 0; i < size; i++) parent[i] = i;
  }

  public int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }

  public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) parent[rootX] = rootY;
  }
}

C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <vector>

class DisjointSet {
public:
  std::vector<int> parent;
  
  DisjointSet(int size) : parent(size) {
    for (int i = 0; i < size; ++i) parent[i] = i;
  }
  
  int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }

  void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) parent[rootX] = rootY;
  }
};

Python Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y

# Example usage:
ds = DisjointSet(5)
ds.union(0, 2)
print(ds.find(2))  # Output: 0

The time complexity for the union and find operations is nearly (O(1)) when path compression and union by rank are used.