0

Union-Find (DSU)

Medium

Each set keeps one representative. Union links two roots, find walks up to the root and flattens the path behind it.

disjoint setpath compressionnear constant
TimeNear O(1) amortised per operation
SpaceO(n)
Inputedges processed in order
0set 01set 12set 23set 34set 45set 5

Start with 6 separate sets, one per node.

components6cycles0
1 / 14
find(x): while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
union(a, b):
ra = find(a); rb = find(b)
if ra == rb: this edge closes a cycle
attach the smaller tree under the larger
Why it matters

Union by size plus path compression keeps trees almost flat.

Practise this
Redundant ConnectionMNumber of ProvincesMAccounts MergeMGraph Valid TreeM
Keyboard
space play← → stepr restartctrl K search

More in Graphs

Breadth First Search
O(V + E)
Depth First Search
O(V + E)
Dijkstra Shortest Path
O(E log V)
Topological Sort (Kahn)
O(V + E)
Kruskal Minimum Spanning Tree
O(E log E)
Flood Fill / Number of Islands
O(rows * cols)
Next visualiser
Kruskal Minimum Spanning Tree