据我的理解,在快速 union 算法中,当要处理一对时,我们首先执行 FIND 操作并检查这些对象所在的树的根是否相等。 如果它们不相等,我们通过链接 2 个不同的根来执行 UNION 操作。
In Sedgewick pg-15 property:1.2-"Suppose that the input pairs come in the order 1-2, then 2-3, then 3-4 and so forth. After N-1 such pairs, we have N objects all in the same set, and the tree that is formed by the quick-union algorithm is a straight line, with N pointing to N-1, which points to N - 2,which points to N - 3, and so forth."
根据我的说法,形成的树有根 1,从 2 到 N 的所有其他对象都是它的子对象 - 当我们扫描 1-2 时,根本身就是它们自己,所以我们将它们链接起来,当我们扫描 2-3 时,根2 的根是 1,3 的根是 3 本身,所以我们链接 1 和 3,而不是 2 和 3。
在这种情况下,树怎么可能是一条直线?
#include <stdio.h>
#define N 10000
main()
{ int i, p, q, t, id[NJ;
for (i = 0; i < N; i++) id[i] = i;
while (scanfC"%d %d\n", &p, &q)==2)
{
for(i=p;i!=id[i];i=id[i]);
for(j=q;j!=id[j];j=id[j]);
if(i==j) continue;
id[i]=j;
printf("%d%d\n",p,q);
}
}
最佳答案
有一种情况可以形成一条直线:
1-2 leads to 1->2
2-3 the root of 2 is 2 and the root of 3 is 3 so link 2 to 3: 1->2->3
3-4 the roots are 3 and 4 so link 3 to 4: 1->2->3->4
...
但是,链接将按照描述的相反方向进行。
关于应用于配对序列时有关快速 union 算法的困惑 : 1-2, 2-3,3-4,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43817235/