Union-Find operations on a tree?

Question

can someone please explain the answer in bold? How it's done?

Below is a sequence of four Union-Find operations (with weighted-union and full com- pression) that led to the following up-tree. What were the last two operations?

Answer: Union(D,A), Union(B,C), Union(D/A,B/C),Find(B/C).

Answer 1

The notation is used because of the sets.

Let us apply the four operations:

Union(D,A) leads to following tree:

   D
  /
 A

Union(B,C) leads to following tree:

   B
  /
 C

Now Union(D/A,B/C) means that because D and A belong to the same set, it does not matter what the first argument is, it can be D or it can be A. Similarly because B and C belong to the same set, it does not matter what the second argument is, it can be B or it can be C, the result will be the same.

The result will be after third operation:

   D
  / \
 A   B
      \
       C

Now because compression is also allowed, the Find(C) operation would result in the tree:

   D
  /|\ 
 A B C

If the fourth operation is Find(B), the tree would remain the same, because when we apply compression after a find operation, we make all the nodes encountered in the path upto the root immediate child of the root, but since we will not encounter C, we will not be able to make C immediate child of D, as it is in final tree.

Correct Answer

The correct sequence of four operations is:

Union(D,A), Union(B,C), Union(D/A,B/C),Find(C).