Union-Find (Disjoint Set)
Software Engineer path · lesson 29 of 99Master the Union-Find data structure. Essential for Kruskal's Algorithm, connected components, and cycle detection in undirected graphs.
Each A-B means union(A, B), applied in order. Repeats are allowed.
Turn both off on the Chain preset and watch pointer hops and tree height grow.
8 separate sets: every node is its own root.
- 1find(x):
- 2 while parent[x] != x: x = parent[x] # walk to the root
- 3 (compression: point every node on the walk at the root)
- 4union(a, b):
- 5 ra, rb = find(a), find(b)
- 6 if ra == rb: return # already connected
- 7 attach the lower-rank root under the other (or rb under ra)
- Pointer hops
- 0 / 9
- Unions
- 0 / 7
Sets: 8
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
union(x, y)
Order the steps of union by rank with path compression.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
Test your knowledge
What is the primary optimization that makes Union-Find nearly constant time?
Write the code
Number of Provinces
function findCircleNum(isConnected) {
// Your code here
}The short version
Think of social networks. When person A befriends person B, their entire groups of friends merge into one giant community. You can quickly check if two random people are in the same extended network.
In more depth
Disjoint Sets
Union-Find is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
Operations:
Optimizations:
When to reach for this
- Find connected components in a graph
- Check if two nodes are connected (fast)
- Cycle detection in undirected graphs
- Kruskal's Algorithm for MST
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required