Disjoint Set Union (DSU)
Definition
Disjoint Set Union (also called Union-Find) is a data structure that tracks elements which are split into one or more disjoint (non-overlapping) sets. Its main job is to quickly tell you if two items belong to the same group or to merge two groups together. 
How it Works
DSU relies on two main operations:
- Find: “Who is the leader of this group?” If item A and item B have the same leader, they are in the same group.
- Union: “Merge these two groups.” We make the leader of one group point to the leader of the other group.
Real-World Analogy: Imagine social circles. Initially, everyone is their own circle.
- If Alice becomes friends with Bob, you Union their circles.
- If Bob is friends with Charlie, you Union their circles.
- Now, to check if Alice knows Charlie (indirectly), you use Find to see if they belong to the same “friendship network” (Set).
Example
Initial: {1}, {2}, {3} Union(1, 2): Sets become {1, 2}, {3}. Leader of 1 is 2. Union(2, 3): Sets become {1, 2, 3}. Leader of 2 is 3. Find(1): Follows path 1 rightarrow 2 rightarrow 3. Leader is 3.
Code Example
PythonJavaCC++
# Disjoint Set Union (Union-Find)
class DSU:
def __init__(self, n):
self.parent = list(range(n))
# Find with Path Compression
def find(self, i):
if self.parent[i] == i:
return i
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
# Union operation
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)
if root_i != root_j:
self.parent[root_i] = root_j
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
print(dsu.find(0) == dsu.find(2)) # True
class DSU {
int[] parent;
DSU(int n) {
parent = new int[n];
for (int i = 0; i < n; i++)
parent[i] = i;
}
// Find with path compression
int find(int i) {
if (parent[i] == i)
return i;
parent[i] = find(parent[i]);
return parent[i];
}
// Union operation
void union(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j)
parent[root_i] = root_j;
}
public static void main(String[] args) {
DSU dsu = new DSU(5);
dsu.union(0, 1);
dsu.union(1, 2);
System.out.println(dsu.find(0) == dsu.find(2)); // true
}
}
#include <stdio.h>
#define N 5
int parent[N];
// Find with path compression
int find(int i) {
if (parent[i] == i)
return i;
parent[i] = find(parent[i]);
return parent[i];
}
// Union
void unionSet(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j)
parent[root_i] = root_j;
}
int main() {
for (int i = 0; i < N; i++)
parent[i] = i;
unionSet(0,1);
unionSet(1,2);
if (find(0) == find(2))
printf("True\n");
else
printf("False\n");
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
class DSU {
public:
vector<int> parent;
DSU(int n) {
parent.resize(n);
for (int i = 0; i < n; i++)
parent[i] = i;
}
// Find with path compression
int find(int i) {
if (parent[i] == i)
return i;
parent[i] = find(parent[i]);
return parent[i];
}
// Union
void unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j)
parent[root_i] = root_j;
}
};
int main() {
DSU dsu(5);
dsu.unite(0,1);
dsu.unite(1,2);
cout << (dsu.find(0) == dsu.find(2)) << endl; // 1 = true
return 0;
}
Complexity Analysis
- Time Complexity: Nearly O(1) (amortized) using Path Compression and Union by Rank. It’s incredibly fast.
- Space Complexity: O(n)
Use Cases
- Kruskal’s Algorithm: Finding the Minimum Spanning Tree in a graph.
- Cycle Detection: Checking if adding a connection in a network creates a loop.
- Image Processing: Finding connected regions of pixels.