algorithm – Union-Find：有效地检索集合的所有成员

我正在使用union-find算法.在我的程序的第一部分中,算法计算大集合E的分区.

之后,我想检索集合S的所有成员,其中包含给定的节点x.

到目前为止,天真地,我正在测试E的所有元素的成员身份.但是昨天我正在阅读“算法导论”(由CLRS,第3版,例如21.3-4),并且在练习中,我发现：

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.

“x集合成员数量的线性”对我的问题将是一个很大的改进！所以,我正在努力解决这个问题……经过一些不成功的尝试,我在Stack Overflow上寻求帮助！

回想一下union-find实现为颠倒树,其中对于每个集合S = {v1,v2,…,vn},你有vn – 1个边,最终具有相同的根(或接收器).

现在,每当您向此树添加边(vi,vj)时,添加另一条边(使用新属性)(vj,vi).删除节点时,也要删除该属性.

请注意,新边缘与旧边缘分开.仅在打印集合中的所有元素时才使用它.并且在原始算法中修改任何原始边缘时修改它.

请注意,此属性实际上是节点列表,但所有列表中的元素总数仍为n – 1.

这将为您提供第二棵树,但不会颠倒.现在,使用root,并进行一些树遍历(使用例如BFS或DFS),您可以打印所有元素.