Union-find (disjoint set union)

The question: are these two in the same group?

Some problems keep asking "are x and y connected?" while new connections keep arriving: friends joining friend circles, computers being cabled into networks, or bank accounts found to belong to the same customer. Groups only ever MERGE. Running a BFS for every question would cost O(V + E) each time. Union-find answers each question in nearly constant time.

A forest of parent pointers

Give every item a parent. At the start, every item is its own parent, so each item is a group of one. The item at the top of a chain, whose parent is itself, is the root, and it acts as the name (the representative) of the whole group. Two items are in the same group exactly when they have the same root.

• find(x): follow parent pointers from x until you reach the root, and return it.
• union(a, b): find the root of a and the root of b. If they differ, make one root the parent of the other. Now both groups share one root.

parent = list(range(5))          # [0, 1, 2, 3, 4]: everyone alone

def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[rb] = ra

union(0, 1)
union(3, 4)
union(1, 4)
print(parent)                                   # Output: [0, 0, 2, 0, 3]
print(find(4) == find(0), find(2) == find(0))   # Output: True False

Two speed-ups

The simple version can build long chains: union in a bad order and find walks O(n) steps. Two small changes fix this.

Path compression: during find, after you reach the root, point every node you passed straight at the root. The next find on any of them takes one step.

def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while x != root:          # second pass: compress the path
        nxt = parent[x]
        parent[x] = root
        x = nxt
    return root

Union by size (or by rank): keep the size of each group at its root, and always hang the SMALLER tree under the larger one. A node then moves one level deeper only when its group at least doubles, so no tree gets taller than about log₂ n.

With both changes, any sequence of m operations on n items takes O(m × α(n)) time, where α is the inverse Ackermann function. It grows so slowly that it is at most 4 for any n you could ever store, so in practice each operation is constant time (amortised: averaged over many operations). The parent and size lists take O(n) space.

Counting groups and classic uses

Keep a count that starts at n. Every union that really joins two different roots lowers it by 1. At the end, count is the number of groups.

• Number of provinces: cities joined directly or through others; union every direct link and read the count.
• Redundant connection: edges of a tree arrive plus one extra. The first edge whose two ends ALREADY have the same root closes a cycle, so it is the extra one.
• Earliest moment everyone is connected: sort events by time and union until the count reaches 1.
• Kruskal's minimum spanning tree (next topic) uses DSU to skip edges that would form a cycle.

DSU cannot easily split a group or delete an edge. If the graph is fixed and you need paths or distances, BFS or DFS is better. If edges arrive one by one and you only merge and ask "same group?", DSU shines.

Common mistakes

• Joining the items instead of their roots (parent[a] = b). Fix: always union find(a) and find(b).
• Comparing parent[a] == parent[b] to test "same group". Parents can differ while roots are equal. Fix: compare find(a) == find(b).
• Lowering the group count even when the two items were already together. Fix: only when the roots differ.
• Labels from 1 to n with a list of size n. Fix: allocate n + 1, or subtract 1.
• A recursive find on a long chain before any compression, which can hit the recursion limit. Fix: an iterative find, or union by size so chains stay short.