Back
+30 XP
Concept

Union-Find (Disjoint Set) with Path Compression

Detecting network partitions, cycles in undirected graphs, and dynamic peer connectivity demands instant group lookups. A Disjoint Set Union (DSU) combining union-by-rank with recursive path compression flattens trees on traversal, achieving nearly constant $O(\alpha(N))$ time complexity 🌐🔗⚡.

python
class DSU:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, i):
        if self.p[i] != i: self.p[i] = self.find(self.p[i])
        return self.p[i]
    def union(self, i, j):
        ri, rj = self.find(i), self.find(j)
        if ri != rj: self.p[ri] = rj

dsu = DSU(4)
dsu.union(0, 1)
print("0 and 1 connected:", dsu.find(0) == dsu.find(1))

# 23. Union-Find (Disjoint Set) with Path Compression In distributed infrastructure, graph routing, and cluster management, you constantly need to answer queries like: *"Are server A and server B in the same network partition?"* or *"Does adding this network cable create a circular loop in the topology?"* 🛑. ```python # The Power of Path Compression: # Before Find: # 3 -> 2 -> 1 -> 0 (Root) [Height = 4, slow traversal] # # Calling find(3): # Recursively links each traversed node directly to root 0! # After Find: # 3 -> 0 # 2 -> 0 # 1 -> 0 [Height = 1, instant O(1) lookups forever!] ``` ### The $O(\alpha(N))$ Complexity Combining **Union by Rank** (attaching the shorter tree to the taller tree) with **Path Compression** flattens the forest completely: - The time complexity drops to $O(\alpha(N))$, where $\alpha$ is the Inverse Ackermann function. - For all practical engineering values (up to $N = 10^{80}$, the number of atoms in the observable universe), $\alpha(N) \le 4$. - In practice, it runs in **pure constant $O(1)$ time** 🌐🔗⚡! --- ### Interactive Pop-Quiz 🧠 #### What does 'Path Compression' do during the find(x) operation in a Disjoint Set Union structure? - [ ] It points visited nodes directly to the root representative, flattening the tree and turning subsequent lookups into $O(1)$ operations 🌐 - [ ] It compresses strings using gzip - [ ] It encrypts network socket connections - [ ] It removes cycles from directed graphs --- ### Practical Challenge 🎯 Implement `UnionFind(size: int)` with `parent: list[int]`, `rank: list[int]`, and `components: int`. Provide `find(x: int) -> int` with path compression, `union(x: int, y: int) -> bool` (returning `False` if already connected, else merging smaller rank under larger rank and decrementing `components`), and `connected(x: int, y: int) -> bool`. Test with 5 nodes, connect 0-1, 1-2, verify `connected(0, 2)` is `True` and `components` is 3. Print results. <details> <summary>Solution</summary> ```python class UnionFind: def __init__(self, size: int): self.parent = list(range(size)) self.rank = [0] * size self.components = size def find(self, x: int) -> int: if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x: int, y: int) -> bool: rx, ry = self.find(x), self.find(y) if rx == ry: return False if self.rank[rx] < self.rank[ry]: self.parent[rx] = ry elif self.rank[rx] > self.rank[ry]: self.parent[ry] = rx else: self.parent[ry] = rx self.rank[rx] += 1 self.components -= 1 return True def connected(self, x: int, y: int) -> bool: return self.find(x) == self.find(y) uf = UnionFind(5) assert uf.components == 5 assert uf.union(0, 1) is True assert uf.union(1, 2) is True assert uf.connected(0, 2) is True assert uf.connected(0, 3) is False assert uf.components == 3 assert uf.union(0, 2) is False print(f"UnionFind verified: 0 and 2 connected, active components={uf.components}") ``` </details>

Checkpoint

What does 'Path Compression' do during the `find(x)` operation in a Disjoint Set Union structure? 🧠

Practice

Implement `UnionFind(size: int)` with `parent: list[int]`, `rank: list[int]`, and `components: int`. Provide `find(x: int) -> int` with path compression, `union(x: int, y: int) -> bool` (returning `False` if already connected, else merging smaller rank under larger rank and decrementing `components`), and `connected(x: int, y: int) -> bool`. Test with 5 nodes, connect 0-1, 1-2, verify `connected(0, 2)` is `True` and `components` is 3. Print results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks