Listing nodes in a data structure with unrelated sets in linear time

Question

I am trying to do this exercise in the Introduction to Algorithms section of Cormen et al, which is related to the Disjoin Set data structure:

Suppose we want to add the PRINT-SET(x) operation, which is given by a node x and prints all elements of x in any order. show how we can add only one attribute for each node in the disjoint set of the forest, so that PRINT-SET(x) takes time linear in the number of members of the set x , and the asymptotic time of other operations has not changed. Suppose we can print each member of a set in O (1) time.

Now I'm absolutely sure that this attribute needs a pointer to the tail so that it can track children.

Since the disjoint set structure already has a parent attribute, find-set(x) can easily print nodes that go in the same direction. But now, having a pointer to the tail, we go in a different direction.

However, I am not sure how I will write an algorithm for this. If anyone could help me in the pseudo code, that would be very appreciated.

Answer 1

Each node must have a next pointer for the next node in the set in which it is located. The nodes in the set must form a circular linked list.

When a singleton set is first created, the node next pointer points to itself.

When you combine a set with node X and install using node Y (and you already noted that these sets differ in normalization for a set of representatives), you merge circular linked lists that you can do by simply changing X.next and Y.next ; therefore, this is operation O(1) .

To list all the elements in the set containing node X , go through a circular linked list starting with X