Union-Find (disjoint-set union)

Why it costs this much

Path compression flattens trees on every find, and union by size keeps trees shallow, so long chains cannot persist.

Code

parent = list(range(n))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]    # path halving: flatten as we climb
        x = parent[x]
    return x
def union(a, b):
    parent[find(a)] = find(b)            # add union by size for the full bound

Common pitfalls

You need both optimizations for the α(n) bound; without them a find can take O(n). Union-Find merges sets but cannot split them.

Operation by operation

Union-Find find and union. Union by rank or size, plus path compression. Without both optimizations, a single operation can cost O(n). α(n) is at most 4 for any practical n.