Use Cases

• Cycle Detection: Union-Find can be used to detect cycles in an undirected graph. If during the edge addition process, the two vertices belong to the same set, it means there's a cycle.
• Minimum Spanning Tree (Kruskal's Algorithm): Union-Find is used in Kruskal's algorithm to efficiently determine whether adding an edge between two vertices creates a cycle in the current forest.
• Connected Components: Union-Find can find all the connected components in an undirected graph by merging sets during traversal.
• Image Processing (Labeling Connected Components): Union-Find can be used in image processing to label connected components of binary images.
• Dynamic Connectivity: Union-Find can efficiently support dynamic connectivity queries, where the connectivity of elements can change over time.

Python

class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.rank = [1] * size
    
    def find(self, x):
        if x != self.root[x]:
            self.root[x] = self.find(self.root[x])
        return self.root[x]
    
    def union(self, x, y):
        rootX, rootY = self.find(x), self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

Cycle Detection with Union Find