Explanation
- Union-Find is a data structure that is used to keep track of a collection of disjoint sets.
- It supports two main operations:
- Find: Determines which set a particular element belongs to.
- Union: Merges two sets into a single set.
- Union-Find is widely used in algorithms like Kruskal’s Minimum Spanning Tree and connected components in a graph.
Steps:
- Find: Use path compression to flatten the tree structure for faster future lookups.
- Union: Use union by rank or size to keep the tree balanced by attaching the smaller tree under the larger tree.
Time Complexity:
- Find and Union operations are nearly O(1) with path compression and union by rank.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [1] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
# Union by rank
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
# Example Usage
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 2)
print(uf.find(0)) # Output: 2
print(uf.find(3)) # Output: 2