The Disjoint Set data structure, also known as Union-Find, is an essential tool in computer science with several practical applications due to its efficient support for the following operations:

1. Find: Determine which subset a particular element is in. This can be used for finding whether two elements are in the same subset. 2. Union: Join two subsets into a single subset.

These operations are fundamental for solving various problems related to partitioning a set into disjoint subsets, where no two subsets overlap. Here are some common applications:

### Applications of Disjoint Set Data Structure

1. Network Connectivity: — In network design, the Disjoint Set is used to detect cycles in a graph, particularly in the Kruskal's algorithm for finding the Minimum Spanning Tree (MST). The algorithm iteratively adds edges to the MST, and the Disjoint Set helps to ensure no cycles are formed. — It is also used to find connected components in a network.

2. Image Processing: — The Disjoint Set is used in image segmentation to group pixels into regions. Each region can be seen as a connected component in the pixel graph.

3. Social Network Analysis: — In social networks, it is used to determine if two users are part of the same group or to find all connected groups of users.

4. Game Development: — Used in union-find operations in game map generation algorithms where different regions need to be connected without cycles.

5. Dynamic Connectivity: — When you need to dynamically connect and disconnect elements and frequently check connectivity among them, Disjoint Set provides an efficient solution.

6. Percolation Theory: — In physics and materials science, the Disjoint Set is used to model percolation systems, where the connectivity of different components needs to be analyzed.

### Why Use Disjoint Set?

- **Efficiency**: The operations `find` and `union` are very efficient, especially with optimizations like path compression and union by rank. These optimizations ensure that the operations are nearly constant time, amortized over a sequence of operations. - **Simplicity**: The data structure is relatively simple to implement and understand, yet it provides powerful capabilities for managing partitions of a set. - **Versatility**: It applies to a wide range of problems in computer science, particularly those involving partitioning or connectivity in graphs.

### Example Use Case: Kruskal's Algorithm

Kruskal's algorithm is used to find the minimum spanning tree (MST) of a graph. Here's how the Disjoint Set is used:

1. **Initialization**: Each vertex is initialized to be its own subset. 2. **Edge Selection**: Edges are sorted by weight. 3. **Edge Addition**: — For each edge, check if the vertices of the edge belong to different subsets using the `find` operation. — If they are in different subsets, add the edge to the MST and union their subsets. — If they are in the same subset, ignore the edge to avoid cycles.

This ensures that the resulting MST is the minimum and spans all vertices without forming any cycles.

In summary, the Disjoint Set data structure is indispensable for efficiently managing and querying disjoint subsets, making it a fundamental tool in algorithm design and many practical applications.

class DisjointSet:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}  # Initialize each node's parent to itself
        self.rank = {v: 0 for v in vertices}    # Initialize the rank of each node to 0

    def find(self, item):
        # Path Compression
        if self.parent[item] != item:
            self.parent[item] = self.find(self.parent[item])
        return self.parent[item]

    def union(self, x, y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        print(f'{x} : {xRoot}, {y} : {yRoot}')
        
        if xRoot == yRoot:
            print('Undirected Graph has a cycle')
        else:
            # Union by rank
            if self.rank[xRoot] < self.rank[yRoot]:
                self.parent[xRoot] = yRoot
            elif self.rank[xRoot] > self.rank[yRoot]:
                self.parent[yRoot] = xRoot
            else:
                self.parent[yRoot] = xRoot
                self.rank[xRoot] += 1