Consider the following problem: Input: G = (V, E), a graph with n = #V and m = #E. Output: a set of Union-Find data structures, for every connected component of G there is exactly one Union-Find data structure.

1 Define an algorithm to solve the above problem. Write the elementary steps in the algorithm with the operations on a Union-Find data structure.

2 Prove the correctness of your algorithm.

3 Express the running time of your algorithm in n and m. Justify the formula for the running time.