Union-Find: retrieve all members of a set efficien

问题:

I'm working with an union-find algorithm. In the first part of my program, the algorithm computes a partition of a big set E.

After that, I want to retrieve all the members of the set S, which contains a given node x.

Until now, naively, I was testing membership of all elements of E to the set S. But yesterday I was reading "Introduction to Algorithms" (by CLRS, 3rd edition, ex. 21.3-4), and, in the exercises, I found that:

Suppose that we wish to add the operation PRINT-SET(x), which is given a node x and prints all the members of x's set, in any order. Show how we can add just a single attribute to each node in a disjoint-set forest so that PRINT-SET(x) takes time linear in the number of members of x's set, and the asymptotic running times of the other operations are unchanged.

"linear in the number of members of x's set" would be a great improvement for my problem! So, I'm trying to solve this exersice... and after some unsuccessful tries, I'm asking help on Stack Overflow!

回答1:

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.

回答2:

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)