Union-Find for Dynamic Connectivity

The operations

A disjoint-set union structure supports:

• find(x): return the representative of x's component,
• union(a,b): merge two components and report whether a merge occurred.

Initially every item is its own parent. A root is a node whose parent is itself.

Two optimisations

Path compression rewires nodes toward the root during find. Union by size or rank attaches the smaller tree below the larger. Together, a sequence of operations takes nearly constant amortised time, written O(α(n)).

Keep metadata—component size, minimum, maximum or sum—on roots. When roots merge, combine their metadata once.

The cycle test

In an undirected graph, adding edge (a,b) creates a cycle exactly when find(a) == find(b) before the union. Kruskal's minimum spanning tree uses the same check after sorting edges by weight.

DSU does not support edge deletion naturally and does not reveal an actual path between vertices. Use graph traversal or more advanced dynamic-connectivity structures for those needs.

Component example

p=list(range(5))
def find(x):
    while x!=p[x]: p[x]=p[p[x]]; x=p[x]
    return x
for a,b in [(0,1),(1,2),(3,4)]: p[find(b)]=find(a)
print(len({find(x) for x in range(5)}))

2

Practice Count Connected Components, Find a Redundant Connection, and Earliest Full Connection.