# 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:

1. 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.
2. 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 = 5uf = NaiveUnionFind()uf.initialize(n)// Initially, each element is its own representative// Union of sets containing elements 1 and 2uf.union(1, 2)// Union of sets containing elements 3 and 4uf.union(3, 4)// Find representative of the set containing element 2rep_of_2 = uf.find(2)// Union of sets containing elements 0 and 3uf.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)):

The most optimized approach for the Union-Find (Disjoint Set Union) algorithm incorporates both path compression and union by rank. This combination ensures a nearly constant amortized time complexity for both the find and union operations. Below is the pseudocode for the optimized Union-Find algorithm:

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.

3. 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.

4. 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 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`

### 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 = 5uf = OptimizedUnionFind(n)# Initially, each element is its own representativeprint("Initial state:", uf.parent)# Union of sets containing elements 1 and 2uf.union(1, 2)print("After union(1, 2):", uf.parent)# Union of sets containing elements 3 and 4uf.union(3, 4)print("After union(3, 4):", uf.parent)# Find representative of the set containing element 2rep_of_2 = uf.find(2)print("Representative of 2:", rep_of_2)# Union of sets containing elements 0 and 3uf.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