Union-find

Applies to: general, python

Union-find (disjoint set union) tracks a collection of groups and answers "are these two connected?" and "merge these groups" in nearly O(1) with path compression. It is the standard tool for connected components and cycle detection while adding edges.

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

See also: graph, tree