Union-Find: retrieve all members of a set efficiently

Recall that union-find is implemented as upside-down tree, where for each set S = {v₁, v₂, ..., v_n}, you have v_{n - 1} edges, that ultimately have the same root (or sink).

Now, whenever you add an edge (v_i, v_j) to this tree, add another edge (using the new attribute) (v_j, v_i). And when you remove a node, remove the attribute as well.

Note that the new edge is separated from the old one. You use it only when printing all elements in a set. And modify it whenever any original edge is modified in the original algorithm.

Note that this attribute is actually a list of nodes, but the total number of elements in all lists combined is still n - 1.

This will give you a second tree, but not upside down. Now, using the root, and doing some tree-traversal (using e.g. BFS or DFS), you can print all elements.

I managed to write another algorithm without the use of lists (it is somewhat more convenient to use with my programming language, i.e. ANSI-C).

I did that with the help of

Printing out nodes in a disjoint-set data structure in linear time.

I found this thread after my first post, my apologies.

In pseudo-code (not yet tested) :

MAKE-SET(x)
    x.p = x
    x.rank = 0
    x.link = x        # Circular linked list

UNION(x,y)
    sx = FIND-SET(x)
    sy = FIND-SET(y)
    if sx != sy
        LINK(sx, sy)

LINK(x,y)
    temp = y.link     # Concatenation
    y.link = x.link   # of the two
    x.link = temp     # circular lists
    if x.rank > y.rank
        y.p = x
    else x.p = y
         if x.rank == y.rank
             y.rank = y.rank + 1

FIND-SET(x)
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p

PRINT-SET(x)
    root = x
    PRINT(x)
    while x.link != root
        x = x.link
        PRINT(x)