1. Suppose we want to add an extra operation, remove(x), which removes x from its current set and places it in its own. Show how to modify the union/?nd algorithm so that the running time of a sequence ofM union, find, and remove operations is O(Mα(M, N)).
2. Show that if all of the unions precede the finds, then the disjoint sets algorithm with path compression requires linear time, even if the unions are done arbitrarily.
3. Prove that if unions are done arbitrarily, but path compression is performed on the finds, then the worst-case running time is 8(M log N).
4. Prove that if unions are done by size and path compression is performed, the worst- case running time is O(Mα(M, N)).