Disjoint Sets Basics

The Idea

Keep one array: parent[x] is who x points at. Follow the pointers and you stop at an element that points at itself — the root, which is the group's name.

find walks up to that root. union finds both roots and hangs one under the other, merging two groups with a single write.

Real-World Example

A photo library clustering faces. When you confirm two clusters are the same person it does not relabel every photo — it points one cluster at the other. Asking "same person?" later just compares the two labels you arrive at.

The Code

parent = list(range(6))          # everyone starts alone: parent[i] == i
def find(x):
    while parent[x] != x:        # walk up to the root
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False    # already one group
    parent[ra] = rb              # hang one root under the other
    return True

union(0, 1); union(1, 2)
print(find(0) == find(2), find(0) == find(3))

parent = [0, 0, 2, 2]
def find(x):
  while parent[x] ___ x:
      x = parent[x]
  return x
print(find(1), find(3))   # 0 2