What is Union-Find?
The Union-Find data structure, also known as Disjoint Set Union (DSU), is used to efficiently handle operations on disjoint sets. It supports two primary operations:
- Find: Determines the set to which a particular element belongs.
- Union: Merges two sets into one.
Union-Find is commonly applied in problems involving connected components, such as Kruskal’s algorithm for finding Minimum Spanning Trees, network connectivity analysis, and social network clustering.
Union-Find Algorithm Pseudocode
Initialize:
parent = [i for i in range(n)]
rank = [1] * n
Find(x):
if x != parent[x]:
parent[x] = Find(parent[x]) # Path compression
return parent[x]
Union(x, y):
root_x = Find(x)
root_y = Find(y)
if root_x != root_y:
if rank[root_x] > rank[root_y]:
parent[root_y] = root_x
elif rank[root_x] < rank[root_y]:
parent[root_x] = root_y
else:
parent[root_y] = root_x
rank[root_x] += 1