MediumHigh Frequency30 min
Union Find (Disjoint Set)
Track connected components efficiently with union by rank and path compression.
Union-Find tracks connected components. find(x) returns representative, union(x,y) merges groups. With path compression + union by rank: O(α(n)) per operation.
Union-Find (Disjoint Set Union)
Union-Find Operations
Number of Connected Components
O(E ┬╖ ╬▒(n)) Γëê O(E)count starts at n, decrements on each successful union of two different components.Step-by-step1 / 4
Graphnodes + edges
01234
Init: parent[i]=i, count=5
Each node is its own root. 5 separate components.