Union-Find: efficiently retrieves all members of a set

Question

I am working with union-find algorithm. In the first part of my program, the algorithm computes the partition of a large set E

After that, I want to get all the elements of the set S that contains the given node x .

So far, naively, I have tested the membership of all elements of E in the set S But yesterday I read "Introduction to Algorithms" (according to CLRS, 3rd edition, for example, 21.3-4), and in the exercises I found that:

Suppose we want to add the PRINT-SET(x) operation, which, given node x , displays all the elements of x in any order. Show how we can add only one attribute for each node to lie in a disjoint forest, so that PRINT-SET(x) takes time, linear in the number of members of set x and asymptotic runtime other operations do not change.

", linear number of x set members" would be a big improvement for my problem! So, I'm trying to solve this problem ... and after some unsuccessful attempts, I turn to Stack Overflow for help!

Answer 1

Recall that union-find is implemented as an inverted tree, where for each set S = {v ₁ , v ₂ , ..., v _n }, you have v _{n - 1} edges, which ultimately have the same root (or receiver).

Now, when 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 delete the node, also remove this attribute.

Please note that the new edge is separate from the old. You use it only when printing all elements in a set. And change it when the original edge changes in the original algorithm.

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

This will give you a second tree, but not upside down. Now, using the root and traversing the tree (using BFS or DFS ), you can print all the elements.

Answer 2

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

I did it with

A listing of nodes in a data structure with unrelated sets in linear time .

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

In pseudo code (not yet verified):

 MAKE-SET(x) xp = 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 yp = x else xp = y if x.rank == y.rank y.rank = y.rank + 1 FIND-SET(x) if x != xp xp = FIND-SET(xp) return xp PRINT-SET(x) root = x PRINT(x) while x.link != root x = x.link PRINT(x)