Data Structures19 sections · 729 units
Open in Course

Section Recap

What you learned

Union-Find tracks connected components efficiently. Core Operations:

  • Find: Return root with path compression
  • Union: Merge by rank/size

Optimizations:

  • Path compression: Flatten tree during find
  • Union by rank: Attach smaller to larger

Applications:

  • Connected components counting
  • Cycle detection in graphs
  • Kruskal's MST algorithm
  • Dynamic connectivity queries

Complexity: O(α(n))O(\alpha(n)) amortized per operation where α\alpha is inverse Ackermann. Space: O(n)O(n) for parent and rank arrays.