我正在使用union-find算法.在我的程序的第一部分,算法计算一个大集的分区E.
之后,我想检索S包含给定节点的集合的所有成员x.
直到现在,天真地,我正在测试E集合中所有元素的成员资格S.但昨天我正在阅读"算法导论"(由CLRS,第3版,例如21.3-4),并且在练习中,我发现:
假设我们希望添加操作
PRINT-SET(x),该操作被赋予一个节点x并x以任何顺序打印所有成员.展示我们如何在一个不相交的林中为每个节点添加一个单独的属性,这样就PRINT-SET(x)可以在所x设置的成员数量上花费时间线性,并且其他操作的渐近运行时间不变.
" x套装成员数量的线性"对我的问题将是一个很大的改进!所以,我正在努力解决这个问题......经过一些不成功的尝试,我在Stack Overflow上寻求帮助!