我正在使用一种union-find算法。在程序的第一部分中，该算法计算了一个大集合的分区E。
union-find
E
之后，我想检索该集合的所有成员S，其中包含一个给定的node x。
S
x
到目前为止，我还只是天真的测试E了set 中所有元素的成员资格S。但是昨天我正在阅读“算法简介”（CLRS，第3版，例如21.3-4），在练习中，我发现：
假设我们希望添加操作PRINT- SET(x)，该操作被赋予一个节点x并x以任意顺序打印的集合的所有成员。演示如何在不相交集林中的每个节点上仅添加一个属性，从而使PRINT- SET(x)时间成线性x集合中成员的数量，而其他运算的渐近运行时间不变。
PRINT- SET(x)
x对于我的问题，“线性集合的成员数线性”将是一个很大的改进！因此，我正在尝试解决此问题，而在尝试失败之后，我正在寻求有关Stack Overflow的帮助！
回想一下，union-find是作为倒置树实现的，其中对于每个集合S = {v 1，v 2，…，v n }，您都有v n-1条边，最终具有相同的根（或 下沉 ）。
现在，每当您向该树添加边缘（v i，v j）时，（使用new属性）添加另一条边缘（v j，v i）。当您删除节点时，也请删除该属性。
请注意，新 边缘 与旧 边缘 分开。 仅 在打印一组中的所有元素 时才 使用它。并在原始算法中修改了任何 原始 边时对其进行修改。
请注意，此属性实际上是节点列表，但所有列表中的元素总数仍为 n-1 。
这将给您第二棵树，但不能 倒立 。现在，使用根并进行一些树遍历（例如使用BFS或DFS），您可以打印所有元素。
