Disjoint Set Data Structure Implementation in Python
A disjoint set data structure, also known as a union-find data structure, is used to keep track of a set of elements partitioned into a number of non-overlapping (disjoint) subsets. It provides two primary operations:
- Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
- Union: Join two subsets into a single subset.
Program Structure
The program implements the Disjoint Set data structure using Python. The main components of the program are as follows:
1. DisjointSet Class
This class encapsulates the functionality of the Disjoint Set data structure. It includes the following methods:
__init__(self, n): Initializes the Disjoint Set withnelements.find(self, x): Finds the representative of the set containingx. It uses path compression for efficiency.union(self, x, y): Unites the sets containingxandy. It uses union by rank to keep the tree shallow.
Python Code Implementation
class DisjointSet:
def __init__(self, n):
"""
Initialize the disjoint set.
:param n: Number of elements in the set.
"""
self.parent = list(range(n)) # Initially, each element is its own parent.
self.rank = [0] * n # Rank is used to keep the tree shallow.
def find(self, x):
"""
Find the representative (root) of the set containing x.
Implements path compression to flatten the structure, improving efficiency.
:param x: Element to find.
:return: Representative of the set containing 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):
"""
Unite the sets containing x and y.
Uses union by rank to attach the smaller tree under the root of the larger tree.
:param x: Element in the first set.
:param y: Element in the second set.
"""
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
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
Explanation
The DisjointSet class maintains two lists:
parent: This list keeps track of the parent of each element. Initially, each element is its own parent.rank: This list is used to keep the tree shallow by attaching the shorter tree under the root of the taller tree during the union operation.
Find Operation
The find method locates the representative of the set containing the element x. It uses path compression, where we make the found root the direct parent of x and its ancestors, flattening the structure and speeding up future operations.
Union Operation
The union method unites the sets containing elements x and y. It uses union by rank, where the tree with the lower rank is attached under the root of the tree with the higher rank. If both trees have the same rank, one tree becomes the root, and its rank is incremented.
Usage Example
ds = DisjointSet(5) # Create a disjoint set with 5 elements (0 to 4).
ds.union(0, 1) # Union the sets containing 0 and 1.
ds.union(1, 2) # Union the sets containing 1 and 2.
print(ds.find(0)) # Output will be the representative of the set containing 0.
print(ds.find(2)) # Output will be the same as the representative of the set containing 0.
print(ds.find(3)) # Output will be the representative of the set containing 3 (which is 3 itself).
This example demonstrates creating a disjoint set with 5 elements, performing union operations, and finding the representative of specific sets.
