Union-Find (Disjoint Set Union) & Path Compression
Union-Find (DSU) tracks elements partitioned into disjoint subsets. With path compression, checking if two nodes belong to the same connected component runs in nearly $O(1)$ amortized time 🧩.
parent = list(range(5))
# Find with path compression:
def find(i):
if parent[i] == i:
return i
parent[i] = find(parent[i]) # Flatten tree! 🧩
return parent[i]
def union(i, j):
root_i, root_j = find(i), find(j)
if root_i != root_j:
parent[root_i] = root_j
union(0, 1); union(1, 2)
print(find(0) == find(2)) # True (Connected!) 🧩
print(find(0) == find(3)) # False (Disconnected) ❌
# 14. Union-Find (Disjoint Set Union) & Path Compression Union-Find (DSU) tracks elements partitioned into disjoint subsets. With path compression, checking if two nodes belong to the same connected component runs in nearly $O(1)$ amortized time 🧩. ```python parent = list(range(5)) # Find with path compression: def find(i): if parent[i] == i: return i parent[i] = find(parent[i]) # Flatten tree! 🧩 return parent[i] def union(i, j): root_i, root_j = find(i), find(j) if root_i != root_j: parent[root_i] = root_j union(0, 1); union(1, 2) print(find(0) == find(2)) # True (Connected!) 🧩 print(find(0) == find(3)) # False (Disconnected) ❌ ``` DSU powers Kruskal's Minimum Spanning Tree algorithm, social network cluster detection, and grid percolation physics! 🧩 --- ### Question What optimization in Union-Find flattens the tree structure during `find()` calls? 🧠 - [ ] a. Path compression (pointing traversed nodes directly to the root) 🧩 - [ ] b. Reallocating memory into a C++ vector - [ ] c. Binary search sorting - [ ] d. Hash table hashing --- ### Challenge Initialize `parent = list(range(4))`. Implement `find(i)` with path compression and `union(i, j)`. Connect `(0, 1)` and `(2, 3)`. Print whether `find(0) == find(1)` and `find(0) == find(2)`. 🎯 <details> <summary>Solution</summary> ```python parent = list(range(4)) def find(i): if parent[i] == i: return i parent[i] = find(parent[i]) return parent[i] def union(i, j): parent[find(i)] = find(j) union(0, 1) union(2, 3) print(find(0) == find(1)) print(find(0) == find(2)) ``` </details>