DSU with Path Compression
Implement find with path compression so that all nodes on the path point directly to the root, achieving near-O(1) amortised find.
DSU with Path Compression is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is Disjoint Set Union?
Disjoint Set Union (DSU), also called Union-Find, is a data structure that maintains a collection of disjoint (non-overlapping) sets. It supports two core operations: find (which set does element x belong to?) and union (merge the sets containing x and y). DSU is ideal for dynamic connectivity problems where groups merge over time but never split.
Every element starts as its own set. As we process edges or relationships, we merge sets together. The challenge is doing this efficiently — naive implementations are O(n) per operation, but with optimisations we approach O(1) amortised.
# Naive DSU without optimisations
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # each node is its own parent
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = pyThe Problem with Naive Find
In the naive DSU, find(x) walks up the parent chain until it reaches a node that points to itself (the root). If the tree is balanced, this is O(log n). But if we always union by linking the second root under the first, we can create a chain (degenerate tree) of length n, making each find O(n).
Consider unioning 0→1→2→3→4 in sequence. Node 0's find call must traverse the entire chain. With path compression, we eliminate this problem by making every visited node point directly to the root during the find operation itself.
# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4] => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4] => find(0) takes 1 step
parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
x = parent[x]
steps += 1
print('Root:', x, 'Steps taken:', steps)Path Compression: One-Pass Recursive
Path compression modifies the find operation so that after finding the root, every node along the path is updated to point directly to the root. Future find calls on those nodes become O(1). The recursive version achieves this elegantly in a single pass.
The key insight: after the recursive call returns the root, we set self.parent[x] = root before returning. This flattens the tree — all nodes on the search path now point directly to the root. This does not change which set a node belongs to; it only shortens future lookup paths.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)Path Compression: Two-Pass Iterative
The iterative version of path compression uses two passes: the first pass walks up to find the root; the second pass revisits every node in the path and updates its parent to the root directly. This avoids recursion stack overhead and is safe for very deep trees near Python's recursion limit.
In both the recursive and iterative approaches the correctness is unchanged — find still returns the same root. The only difference is the parent pointers being updated as a side effect, which makes all future finds on those nodes O(1).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root] # first pass: find root
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root # second pass: compress
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
return True
return False # already connected
dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after find(0):', dsu.parent[:])Amortised Complexity of Path Compression
Path compression alone achieves an amortised time of O(log n) per operation over a sequence of m operations. Each find operation may be expensive the first time a chain is traversed, but it flattens that chain so every subsequent find on those nodes is O(1). The total work is spread across many operations.
The formal analysis uses the potential function method: the potential of the DSU decreases every time a node's parent shortens, and this decrease pays for the traversal cost. Without union by rank, path compression alone gives O(log n) amortised — already a huge improvement over the naive O(n).
# Demonstrating amortised benefit
import time
def build_chain(n):
parent = list(range(n))
for i in range(n - 1):
parent[i] = i + 1 # chain: 0->1->2->...->n-1
return parent
n = 1000
parent = build_chain(n)
# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
root = parent[root]
# Compress
while parent[x] != root:
nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0]) # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')Connected Components Count
A common DSU application is counting connected components in a graph. We initialise a components counter equal to n (one per node). Each successful union (merging two different sets) decrements the counter by 1. At the end, the counter holds the number of distinct components.
This is more efficient than running BFS or DFS for connectivity queries, especially when edges arrive incrementally (online). The DSU processes each edge in nearly O(1) amortised time regardless of when it arrives.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
self.parent[px] = py
self.components -= 1
return True
dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
dsu.union(u, v)
print('Components:', dsu.components) # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')DSU for Graph Problems: Number of Provinces
The Number of Provinces problem gives an n×n adjacency matrix and asks how many groups of directly or indirectly connected cities exist. This is exactly a connected-components problem that DSU solves cleanly. We iterate over all pairs (i, j) where isConnected[i][j] == 1 and call union(i, j).
After processing all connections, dsu.components is the answer. This is simpler and faster than running BFS from every unvisited node, and it handles the matrix representation directly without building an adjacency list first.
def find_provinces(isConnected):
n = len(isConnected)
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py:
parent[px] = py
return True
return False
count = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
if union(i, j):
count -= 1
return count
matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix)) # 2: cities {0,1} and {2}Path Compression Variants: Halving
Beyond the two-pass compression, there is a simpler one-pass variant called path halving: as we walk up the chain, we make every node point to its grandparent instead of its parent. This halves the path length each traversal without a second pass and achieves the same O(alpha(n)) amortised complexity when combined with union by rank.
Path halving is often preferred in competitive programming because it is a single clean loop with no recursion or second traversal. Each step does self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].
class DSUHalving:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # point to grandparent
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))Checking Connectivity After Unions
To check if two nodes are connected (in the same component), call find(x) == find(y). If both return the same root, they are in the same component. This is the connected query, and with path compression it runs in near-O(1) amortised time.
In interview problems, connectivity queries often appear interleaved with union operations. DSU handles both online — you can alternate unions and queries in any order. This distinguishes DSU from static-graph algorithms like BFS/DFS, which must re-run after each structural change.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
def connected(self, x, y):
return self.find(x) == self.find(y)
dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7)) # True: 0-3-7
print(dsu.connected(0, 5)) # False: different components
print(dsu.connected(1, 5)) # True: 1-5Common Pitfalls in DSU Implementation
A frequent mistake is calling find and then modifying parent incorrectly. Always call find on both elements before checking equality — otherwise you may compare a node to its own root incorrectly. Another pitfall is forgetting that union should be a no-op when both elements already share a root.
In Python, the recursion depth limit (default 1000) can cause RecursionError for large chains with recursive find. Either use the iterative two-pass version, increase the limit with sys.setrecursionlimit, or use path halving iteratively to avoid deep recursion altogether.
import sys
sys.setrecursionlimit(10000) # needed for large recursive DSU
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
# Safe iterative path compression
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # already same component — do nothing
self.parent[px] = py
return True
dsu = DSU(5)
print(dsu.union(0, 1)) # True: merged
print(dsu.union(0, 1)) # False: already merged — no double-countingDSU Size Tracking
In some problems you need the size of each component, not just its root. Add a size array initialised to all 1s. When merging two components, add the size of the smaller root to the larger root. This enables O(1) component-size queries after any union.
Size tracking is also the basis for union by size (an alternative to union by rank): always attach the smaller tree under the larger tree's root. This guarantees the tree height stays O(log n), giving the same asymptotic guarantee as union by rank.
class DSUWithSize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.size[px] < self.size[py]:
px, py = py, px # attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
def get_size(self, x):
return self.size[self.find(x)]
dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0)) # 3
print('Size of component containing 3:', dsu.get_size(3)) # 2
print('Size of component containing 5:', dsu.get_size(5)) # 1Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: DSU maintains disjoint sets with find and union operations, path compression flattens the tree by pointing all traversed nodes directly to the root, and this gives near-O(1) amortised find performance. Next up we explore union by rank, which keeps trees shallow from the top down to achieve the inverse Ackermann bound.
Frequently asked questions
Is the “DSU with Path Compression” lesson free?
Yes — the full text of “DSU with Path Compression” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “DSU with Path Compression”?
Implement find with path compression so that all nodes on the path point directly to the root, achieving near-O(1) amortised find. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “DSU with Path Compression” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.