Union Find

Disjoint Set Union with path compression and union by rank.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

DSU Basics

Disjoint Set Union (DSU) maintains a collection of disjoint sets. Supports: Find(x) — returns set representative; Union(x,y) — merges sets containing x and y. Initially each element in own set.

Gobasic-dsu.go

38 linesLn 1, Col 1Go

Parent array: parent[x] = x means x is root. Find with path compression flattens tree. Union by rank keeps tree shallow.

Path Compression

During Find, make every node on path point directly to root. Amortizes to nearly O(1) (inverse Ackermann function α(n)).

Union by Rank/Size

Attach smaller tree under larger tree's root. Rank approximates log₂(size). Keeps tree height logarithmic. With path compression: O(α(n)) amortized.

Applications

Cycle detection in undirected graph: Union edge endpoints; if already same set, cycle.
Kruskal's MST: Sort edges, add if not forming cycle (DSU check with DSU.
Connected components: After all unions, count unique roots.
Dynamic connectivity: Online connectivity queries.
Percolation: Grid connectivity with DSU.
Minimum spanning tree verification: DSU checks if adding edge creates cycle.

Gokruskal's-mst-with-dsu.go

21 linesLn 1, Col 1Go

Sort edges by weight. Add if endpoints in different components (Union returns true). Stop when n-1 edges added.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.