Union-Find: Who Is in Which Group?

Merging groups

Imagine people becoming friends one pair at a time, and you keep asking “are these two in the same friend group?”. Union-find (also called a disjoint set) answers in almost O(1).

Every group has a leader

• Each person points to a parent. Following parents eventually reaches the group's leader (who points to themselves).
• find(x) – follow the parents up to the leader.
• union(a, b) – find both leaders; if they differ, make one leader point to the other. The groups are merged.

Think of it like this: Every club has a president. To check if two people are in the same club, ask each “who's your president?”. When two clubs merge, one president simply reports to the other.

parent = list(range(6))          # everyone starts as their own leader

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path compression: skip a level
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False             # already in the same group
    parent[rb] = ra
    return True

union(0, 1)
union(2, 3)
union(1, 3)
print(find(0) == find(2))        # 0-1 and 2-3 got joined through 1-3
print(find(0) == find(4))
groups = len({find(x) for x in range(6)})
print("groups:", groups)

Output

True
False
groups: 3

Path compression (the line that skips a level) keeps the chains short, so each operation is practically O(1).

Remember: Union-find is perfect when groups only ever merge. It also detects cycles: if union(a, b) returns False, a and b were already connected, so the new edge closes a loop.