Explanation
- The Disjoint-set (or Union-Find) data structure is used to efficiently manage a collection of disjoint sets. It supports two main operations: find (finding the representative or leader of a set) and union (merging two sets).
Steps
- Find operation: Find the representative (or parent) of an element, typically using path compression for efficiency.
- Union operation: Combine two sets by linking the root of one set to the root of the other, using union by rank or size for efficiency.
Time Complexity
- Time complexity: O(α(n)), where α is the inverse Ackermann function, which grows extremely slowly, almost constant for all practical purposes.
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * n
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):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
# Union by rank
if self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
elif self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
# Example usage
ds = DisjointSet(5)
ds.union(0, 1)
ds.union(1, 2)
print(ds.find(0)) # Should print 0
print(ds.find(2)) # Should print 0