Union Find Problem In Python
Introduction Union Find In Python(Disjoint Set)
Disjoint set data structure, often referred to as Union-Find, is a fundamental and versatile concept in computer science and graph theory. It is designed to efficiently manage a partition of a finite set into disjoint subsets and answer queries about the connectivity or relationships between elements.
The primary operations supported by the disjoint set data structure are union and find. The union operation merges two subsets into a single set, effectively combining their elements.
What is Union Find?
Union-Find, also known as disjoint set union (DSU) or simply as Union-Find, is a data structure used to efficiently manage a partition of a finite set into disjoint subsets. This data structure is particularly useful for solving problems related to dynamic connectivity in graphs or sets.
Disjoint Set:
Disjoint sets are sets that are considered disjoint if their intersection is empty, denoted as ∅ (NULL). The Disjoint-Set data structure is designed to maintain a collection of elements organized into distinct, non-overlapping subsets. Each element belongs to precisely one subset, and the primary characteristic of disjoint sets is that the intersection of any two sets is an empty set, indicating no common elements between them. This data structure is particularly useful for efficiently managing and querying partitioned sets in various algorithmic applications.
Union Find:
The Union-Find algorithm is a versatile data structure that executes two essential operations:
- Find: The Find operation is employed to determine the subset to which a specific element ‘k’ belongs. This operation is commonly utilized to ascertain whether two elements are members of the same subset or not. By using the Find operation, one can efficiently identify the representative or leader element of the subset to which ‘k’ belongs.
- Union: The Union operation is instrumental in merging two subsets into a single cohesive set. When a Union query, such as Union(x, y), is executed, it effectively combines the set containing element ‘x’ with the set containing element ‘y.’ This process of merging subsets facilitates the establishment of connections between different elements and helps in the formation of larger, interconnected sets.
Algorithm:
Naive Implementation:
Pseudocode for the naive implementation of Union-Find (Disjoint Set Union) algorithm:
1. Initialization (initialize function):
Time Complexity: O(n)
Explanation: The initialization involves creating an array of size n and assigning each element to be its own parent. This process runs in linear time, as each element needs to be processed once.
2. Find (find function):
Time Complexity: O(n)
Explanation: The find operation involves following parent pointers until the representative is reached. In the worst case, the depth of the tree can be n, leading to a time complexity of O(n). This is because, in the absence of optimizations, the tree can become a linear chain.
3. Union (union function):
Time Complexity: O(1)
Explanation: The union operation involves updating the parent pointer of one set’s representative to point to the representative of the other set. This operation is constant time because it only requires updating a single pointer.
class NaiveUnionFind:
function initialize(n):
// Create a disjoint set with n elements
parent = array of size n
for i from 0 to n-1:
parent[i] = i
function find(x):
// Find the representative of the set to which x belongs
if parent[x] equals x:
return x
else:
return find(parent[x])
function union(x, y):
// Union of two sets by setting the representative of one as the parent of the other
root_x = find(x)
root_y = find(y)
parent[root_x] = root_y
// Example Usage:
n = 5
uf = NaiveUnionFind()
uf.initialize(n)
// Initially, each element is its own representative
// Union of sets containing elements 1 and 2
uf.union(1, 2)
// Union of sets containing elements 3 and 4
uf.union(3, 4)
// Find representative of the set containing element 2
rep_of_2 = uf.find(2)
// Union of sets containing elements 0 and 3
uf.union(0, 3)
Optimization 1 (Path Compression):
Pseudocode for the Union-Find algorithm with the Path Compression optimization:
1. Initialization (initialize function):
This function initializes the disjoint set data structure with arrays parent and rank. The parent array represents the parent pointers, and the rank array is used to keep track of the depth of each tree.
2. Find (find function):
The find operation with path compression involves recursively finding the representative of the set to which ‘x’ belongs. Along the way, it updates the parent pointers of the traversed elements to directly point to the representative, effectively compressing the paths.
3. Union (union function):
The union operation uses both union by rank and path compression. It first finds the representatives of the sets containing ‘x’ and ‘y’, then attaches the smaller tree to the root of the larger tree. If the trees have equal rank, one tree is chosen as the root, and the rank of the new root is incremented.
class PathCompressionUnionFind:
function initialize(n):
// Create a disjoint set with n elements
parent = array of size n
rank = array of size n
for i from 0 to n-1:
parent[i] = i
rank[i] = 0
function find(x):
// Find the representative of the set to which x belongs with path compression
if parent[x] ≠ x:
parent[x] = find(parent[x]) // Path compression: update parent to the representative
return parent[x]
function union(x, y):
// Union of two sets by rank and path compression
root_x = find(x)
root_y = find(y)
if root_x ≠ root_y:
// Attach the smaller tree to the root of the larger tree
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
else if rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_x] = root_y
rank[root_y] += 1
Optimization 2(Union by Rank):
Pseudocode for the Union-Find algorithm with the Union by Rank optimization:
1. Initialization (initialize function):
This function initializes the disjoint set data structure with arrays parent and rank. The parent array represents the parent pointers, and the rank array is used to keep track of the depth of each tree.
2. Find (find function):
The find operation with path compression involves recursively finding the representative of the set to which ‘x’ belongs. Along the way, it updates the parent pointers of the traversed elements to directly point to the representative, effectively compressing the paths.
3. Union (union function):
The union operation uses both union by rank and path compression. It first finds the representatives of the sets containing ‘x’ and ‘y’. It then attaches the smaller tree to the root of the larger tree based on rank. If the ranks are equal, one tree is chosen as the root, and the rank of the new root is incremented.
class UnionByRankPathCompressionUnionFind:
function initialize(n):
// Create a disjoint set with n elements
parent = array of size n
rank = array of size n
for i from 0 to n-1:
parent[i] = i
rank[i] = 0
function find(x):
// Find the representative of the set to which x belongs with path compression
if parent[x] ≠ x:
parent[x] = find(parent[x]) // Path compression: update parent to the representative
return parent[x]
function union(x, y):
// Union of two sets by rank and path compression
root_x = find(x)
root_y = find(y)
if root_x ≠ root_y:
// Attach the smaller tree to the root of the larger tree based on rank
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
else if rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
// If ranks are equal, choose one as the root and increment its rank
parent[root_x] = root_y
rank[root_y] += 1
Most Optimized Approach (Union-Find (Disjoint Set Union)):
class OptimizedUnionFind:
function initialize(n):
// Create a disjoint set with n elements
parent = array of size n
rank = array of size n
for i from 0 to n-1:
parent[i] = i
rank[i] = 0
function find(x):
// Find the representative of the set to which x belongs with path compression
if parent[x] ≠ x:
parent[x] = find(parent[x]) // Path compression: update parent to the representative
return parent[x]
function union(x, y):
// Union of two sets by rank and path compression
root_x = find(x)
root_y = find(y)
if root_x ≠ root_y:
// Attach the smaller tree to the root of the larger tree based on rank
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
else if rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
// If ranks are equal, choose one as the root and increment its rank
parent[root_x] = root_y
rank[root_y] += 1
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code Implementation of Union Find:
class OptimizedUnionFind:
def __init__(self, n):
# Create a disjoint set with n elements
self.parent = [i for i in range(n)]
self.rank = [0] * n
def find(self, x):
# Find the representative of the set to which x belongs with path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression: update parent to the representative
return self.parent[x]
def union(self, x, y):
# Union of two sets by rank and path compression
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
# Attach the smaller tree to the root of the larger tree based on rank
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
# If ranks are equal, choose one as the root and increment its rank
self.parent[root_x] = root_y
self.rank[root_y] += 1
# Example Usage:
n = 5
uf = OptimizedUnionFind(n)
# Initially, each element is its own representative
print("Initial state:", uf.parent)
# Union of sets containing elements 1 and 2
uf.union(1, 2)
print("After union(1, 2):", uf.parent)
# Union of sets containing elements 3 and 4
uf.union(3, 4)
print("After union(3, 4):", uf.parent)
# Find representative of the set containing element 2
rep_of_2 = uf.find(2)
print("Representative of 2:", rep_of_2)
# Union of sets containing elements 0 and 3
uf.union(0, 3)
print("After union(0, 3):", uf.parent)
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment