Disjoint-Set Union

Union-Find: track which elements are in the same group, with near-$O(1)$ union and find.

Intermediate

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

Path compression + union by rank gives inverse-Ackermann time. Used in Kruskal's algorithm and connectivity problems.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)