Union-Find

Union-Find is a data structure for maintaining disjoint sets. It supports finding an element’s representative and unioning two groups.

It is especially useful for connectivity problems where edges are added over time.

Core Idea

Each element points to a parent. A representative, or root, identifies the whole group. find(x) returns the representative for x. union(a, b) merges the groups containing a and b.

If two elements have the same representative, they are in the same group.

Python Example

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
 
    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a

This basic version shows the interface before optimizations.

Common Confusions

Union-Find answers connectivity membership. It does not tell the actual path between two vertices.

The basic version can become slow if parent chains become long. Practical versions add path compression and union by rank or size.

When To Use It

Use Union-Find for dynamic connectivity, cycle detection in undirected edge processing, Kruskal’s algorithm, and grouping problems where merges are frequent.