A disjoint set is a data structure that keeps track of a partitioning of a set into disjoint subsets. It provides two main operations: finding the representative (root) of a set to which an element belongs and merging two sets together.

There are several implementations of disjoint set data structure, and one popular approach is using the Union-Find algorithm. The Union-Find data structure efficiently performs both the find and union operations.

Here's a step-by-step explanation of the Union-Find algorithm:

1. Initialization: Each element initially belongs to its own disjoint set, and the representative of each set is itself.

2. Find operation: Given an element, find its representative (root) of the set to which it belongs. This operation traverses the parent pointers until it reaches the root node.

3. Union operation: Given two elements, merge the sets to which they belong by making the root of one set the parent of the root of the other set.

4. Path compression optimization: During the find operation, after finding the root of a set, update the parent pointers of all traversed nodes to directly point to the root. This optimization flattens the tree structure and improves the efficiency of future find operations.

Here's an example implementation of the Union-Find (disjoint set) data structure in Python:

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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:
            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:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

# Usage example
n = 6 # Number of elements
ds = DisjointSet(n)

ds.union(0, 1)
ds.union(1, 2)
ds.union(3, 4)
ds.union(4, 5)

print(ds.find(2)) # Output: 0 (representative of the set containing element 2)
print(ds.find(5)) # Output: 3 (representative of the set containing element 5)

In this implementation, the `DisjointSet` class maintains two arrays: `parent` and `rank`. The `parent` array stores the parent of each element, and the `rank` array keeps track of the height of the trees (or ranks) during union operations. The `find` operation uses path compression optimization to flatten the tree, and the `union` operation merges sets based on the rank of their roots.

The time complexity of the Union-Find algorithm is nearly constant on average for each operation (amortized time complexity), resulting in a very efficient data structure for handling disjoint sets.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc