<aside> 🤝

L10 — Union-Find covers the Union-Find (Disjoint Set) data structure: dynamic connectivity, equivalence classes, and the three progressively faster implementations — Quick Find (eager, O(n) union), Quick Union (lazy, tree-based, O(n) worst case), and Weighted Quick Union (balanced trees, O(log n)). It also introduces path compression to achieve near-constant time operations, and demonstrates applications including minimum spanning trees and cycle detection.

</aside>

📋 At a Glance

• [ ] Understand the Union-Find problem: fixed set of elements, dynamic grouping via union, and connectivity queries via find
• [ ] Know the three conditions: fixed number of elements, no insertions or deletions, each element belongs to exactly one group
• [ ] Define equivalence classes and the three required properties: reflexive, symmetric, transitive
• [ ] Give real-world examples of equivalence classes (pixels in images, machines in networks, social network groups)
• [ ] Know the Union-Find API: init(n), find(p), union(p, q), isConnected(p, q)
• [ ] Trace through a Quick Find example using an ID array where id[i] stores the group label directly
• [ ] Know Quick Find complexity: init O(n), find O(1), union O(n) — union is the bottleneck
• [ ] Trace through a Quick Union example using a parent-pointer tree (forest structure)
• [ ] Know Quick Union complexity: init O(n), find O(n) worst case, union O(n) worst case
• [ ] Understand why Quick Union can degenerate into a tall skinny tree (worst case)
• [ ] Explain Weighted Quick Union: always attach the smaller tree under the root of the larger tree
• [ ] Know Weighted Quick Union complexity: init O(n), find O(log n), union O(log n)
• [ ] Explain path compression: during find, flatten the tree by linking all visited nodes directly to the root
• [ ] Know that path compression is only applied when find is called — not eagerly across the whole structure
• [ ] Know the combined complexity with weighted union + path compression: O(log n)* (iterated logarithm, effectively constant)
• [ ] Understand log* n: the number of times you must take log₂ before reaching ≤ 1 — for all practical data, log* n ≤ 5
• [ ] Trace through a Minimum Spanning Tree example using Union-Find (Kruskal's algorithm)