Common Union-Find Bugs

Bug 1: Forgetting path compression in find

# Wrong - returns root without compressing
def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

# Correct - compresses path
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

Bug 2: Union returning wrong result

The union function should return whether the union happened (True if different components).

Bug 3: Off-by-one in node indexing

If nodes are 1-indexed but array is 0-indexed, allocate $n+1$ elements.

Bug 4: Not handling self-loops

union(x, x) should return False without modifying structure.

Always test: single element, two elements, chain of unions, self-loop.