8.13

Idea. Store each connected component in a Disjoint–Set Union (DSU). For every set–representative keep a meld-able priority queue (e.g. a Leftist/Skew/Pairs/Fibonacci heap) that contains all edges whose both ends currently lie in that component.

Data kept for every vertex
• parent[v] – DSU parent.
• rank[v] – DSU rank/size.
• heap[v] – pointer to the heap that belongs to the set whose representative is find(v) (meaningful only for representatives).

Lazy deletion. When components merge, many old edges in their heaps may now connect two different components. We do not clean them eagerly; instead, whenever we ask for the minimum edge of a component we repeatedly discard the top element until its two endpoints are still in the same set.

make_set(v): parent[v] ← v , rank[v] ← 0 heap[v] ← empty heap add_edge(u,v,w): // optional – if edges arrive online r ← find(u), s ← find(v) if r = s: heap[r].insert( (w,u,v) ) find(v): if parent[v] ≠ v: parent[v] ← find(parent[v]) return parent[v] merge(a,b): // operation (a) r ← find(a), s ← find(b) if r = s: return if rank[r] < rank[s]: swap(r,s) parent[s] ← r if rank[r] = rank[s]: rank[r]++ heap[r] ← meld( heap[r] , heap[s] ) min_edge(v): // operation (c) r ← find(v) while heap[r] not empty: (w,u,x) ← heap[r].min() if find(u)=r and find(x)=r: return (w,u,x) heap[r].delete_min() // stale edge, discard return ⌀ // no edge inside component

Complexities (n vertices, m edges)
• find – O(α(n)) amortized (inverse Ackermann).
• merge – O(α(n)) for DSU + O(1) amortized for meld with Fibonacci (O(log n) with leftist/skew).
• min_edge – O(α(n)) expected, because each stale edge is removed only once and every valid minimum is returned in O(1).

Thus the structure supports the required operations efficiently while always giving the current minimum-weight edge contained entirely inside any component.

Back to Chapter 8