Disjoint Set Union

Works in $O(\log n)$ time.

• Always connect the representative of the smaller set to the representative of the larger set (or if the sets are of equal size, we can make an arbitrary choice).

Implementation

• link contains for each element the next element in the chain or the element itself if it is a representative
• size indicates for each representative the size of the corresponding set

for (int i = 1; i <= n; i++) link[i] = i; 
for (int i = 1; i <= n; i++) size[i] = 1;
 
 
int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}
 
bool same(int a, int b) { 
	return find(a) == find(b); 						
}
 
void unite(int a, int b) { 
	a = find(a); 
	b = find(b); 
	if (size[a] > size[b]) swap(a,b);  // Connect the smaller set to the bigger set
	size[b] += size[a]; 
	link[a] = b; 
}

Optimizations

Path Compression Optimization The find function is naive and can take $O(n)$. We can optimize it so every time you call find, you update the parent directly to the root.

int find(int x) { // Naive
	while (x != link[x]) x = link[x]; 
	return x; 
}
 
int find(int x) { // Optimized
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}
 
 
 

This allows us to achieve $O(\log n)$ on average.

2. Union by size (already implemented) in the logic above

Applications

• Kruskal’s Algorithm for finding the Minimum Spanning Tree