Core Operations

  • Identify the operations of the Union-Find data structure.

The core operations of Union-Find data structure includes:

makeSet(x)   // create and return singleton set with x as element.
find(x)      // return some representation of the set to which x belongs.
union(x,y)   // merge the sets containing x and y.

The Union-Find typically includes the following operations too:

connected(x,y)  // return true if x & y are in the same set.
count()         // return number of (disjoint) sets.

There are two general approaches to implement Union-Find data structure:

  • Quick Find
  • Quick Union