Pattern 3: Union-Find (disjoint sets)

How to quickly answer "are these two nodes in the same group?" while groups keep merging? Union-Find (or DSU — disjoint set union) does exactly that: grouping and querying connection in almost constant time.

🎯

Try it first: Graph Valid Tree

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Given n nodes and a list of undirected edges, return true if the graph forms a valid tree (fully connected and without cycles).

Example: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] → true. With [[0,1],[1,2],[2,3],[1,3],[1,4]] → false (it has a cycle).

Carregando editor…

Tried it? To check whether it is a tree, you need two things: connected and without a cycle. Union-Find detects the cycle elegantly — when an edge links two nodes that were already in the same group.

The theory: each group has a "representative"

The idea of Union-Find: each node points to a "parent", and following the parents you reach the representative (root) of the group. Two nodes are in the same group if they have the same representative. Two operations:

find(x): climbs through the parents up to the root — the representative of x's group.
union(a, b): links the root of one group to the root of the other, merging them.

parent = [0, 1, 2, 3, 4]   # at first, each node is its own group

union(0,1): parent[0] = 1      groups: {0,1} {2} {3} {4}
union(2,3): parent[2] = 3      groups: {0,1} {2,3} {4}
find(0) == find(1)? yes → connected
find(0) == find(2)? no → different groups

Two optimizations make each operation almost O(1) (amortized, O(α(n)) — practically constant):

Path compression: in find, point the nodes directly to the root.
Union by size/height: always link the smaller tree under the larger one.

Detecting a cycle with Union-Find

Here is the trick for undirected graphs: when processing an edge (a, b), if a and b already have the same representative, then there was already a path between them — this edge closes a cycle. If they have different representatives, merge them.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False        # already connected ⇒ cycle!
        self.parent[ra] = rb
        return True             # merged two groups

Carregando editor…

Graph Valid Tree, in one sentence

A tree with n nodes has exactly n-1 edges and is connected. With Union-Find: if there are not n-1 edges, it is not a tree already; otherwise, merge each edge — if any closes a cycle (union returns False), it is not a tree. With n-1 edges and no cycle, the graph is necessarily connected. Almost O(n + e).

Union-Find or DFS/BFS?

Both find connected components. When to prefer Union-Find?

Situation	Best
Components of a static graph	DFS/BFS or Union-Find (either way)
Edges arriving gradually ("connected now?")	Union-Find (updates in ~O(1))
Detect a cycle in an undirected graph	Union-Find (edge within the same group)
Need the path or the visit order	DFS/BFS

🧠 Review quiz

0/4

1. How does Union-Find decide whether two nodes are in the same group?

2. How does Union-Find detect a cycle in an undirected graph?

3. Why does a valid tree with n nodes need exactly n-1 edges?

4. When is Union-Find clearly preferable to DFS/BFS?

Summary

Union-Find: each group has a representative; find finds the root, union merges groups. Almost O(1) per operation (with path compression).
Detects a cycle (undirected): an edge between nodes already in the same group.
Graph Valid Tree: n-1 edges + no cycle ⇒ tree.
Prefer Union-Find for dynamic connections and undirected cycle detection.

Next lesson: remembering that a grid is a graph — and propagating from several sources at the same time.

All lessons in this section