6.4. Names of Components

Try these first

1. 1.

   What two operations are fundamental in the Union-Find data structure?

   Hint

   Think of what it means to locate and combine elements.

2. 2.

   Why do we avoid merging components of the same size in Union-Find?

   Hint

   Consider tree structure and height.

3. 3.

   What are the two main operations provided by the Union-Find data structure?

   • Add and Remove
   • Find and Union
   • Sort and Search

   Hint

   Think about how elements are connected.

4. 4.

   True or False: Union-Find can store overlapping components.

   • True
   • False

   Hint

   Consider the word 'disjoint'.

5. 5.

   In a graph of 8 vertices, you perform a sequence of union operations such that the size of components doubles every step until you reach the maximum of 8. Describe how you would implement this using a Union-Find structure and the expected time complexity.

   Hint

   Reflect on how merging affects components overall.

6. 6.

   Consider an instance where you need to repeatedly add edges to a graph using Kruskal's algorithm with the Union-Find data structure. Analyze how the choice of the merging method might affect the performance of the algorithm.

   Hint

   Think about how the structure of components influences operational time.