Suppose we want to extend the union-find data structure to support the operation Reset(c), which takes as input the name of a component c and then breaks up c into singleton components, like MakeUnionFind().
For instance if c = 3 and c currently consists of {1,3,7}, then Reset(c) will produce three components called 1, 3 and 7 consisting of {1}, {3} and {7}, respectively.
Which of the following is correct about the cost of adding Reset(c) to the array and pointer implementations of union-find discussed in the lecture?
- Array representation: O(n), Pointer representation: O(n)
- Array representation: O(size(c)), Pointer representation: O(n)
- Array representation: O(n), Pointer representation: O(size(c))
- Array representation: O(size(c)), Pointer representation: O(size(c))