Data structure containing multiple sets.

  • Stored as array and Tree
  • Make set: Initialize singleton (=single element) set for each element
  • Union set
    • Find owner of both element
    • Make tree with one as parent
  • Find owner of elem

Path compression: once you find something, directly attach all nodes of the path to that root ⇒ with path compression, a sequence of union-find operations are where is the minimum such that the Ackerman Function