0

据我了解，当处理一对时，我们首先执行 FIND 操作并检查存在这些对象的树的根是否相等。在它们不相等的情况下，我们通过链接 2 个不同的根来执行 UNION 操作。

在 Sedgewick pg-15 property:1.2-"假设输入对的顺序是 1-2，然后是 2-3，然后是 3-4，依此类推。在 N-1 个这样的对之后，我们有 N 个对象都在同样的集合，快速联合算法形成的树是一条直线，N指向N-1，N-1指向N-2，N-3指向N-3，以此类推。”

根据我的说法，形成的树有根 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);

}
}
4

2 回答 2

0

有一种情况可以形成一条直线：

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
...

然而，链接将按照所描述的相反方向进行。

于 2017-05-06T06:16:51.057 回答
0

找到某种方法来可视化所产生的联合查找结构可能会对您有所帮助。使用使用 Sedgwick 提供的静态数据的代码的清理版本，并生成最终结构的点文件以进行可视化，得到这个点文件（箭头含义x->id[x]）。

digraph unionfind {
    "1" -> "2"
    "2" -> "3"
    "3" -> "4"
}

使用http://dreampuf.github.io/GraphvizOnline/呈现为该图

1->2->3->4

这是带有点文件生成的清理代码。您可以尝试更改data数组以查看不同顺序或联合的效果。可视化图不包括结构中既不是另一个节点的父节点也不是子节点的节点。

#include <stdio.h>

#define N 10000

int data[][2] = {
    {1, 2},
    {2, 3},
    {3, 4}
};

int main() {
    int id[N];
    for (int i=0; i<N; i++) id[i] = i;

    for (int di=0; di<sizeof(data)/sizeof(data[0]); di++) {
        int p = data[di][0];
        int q = data[di][1];

        int i, j;
        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("digraph unionfind {\n");
    for (int i=0; i<N; i++) {
        if (id[i] == i) continue;
        printf("    \"%d\" -> \"%d\"\n", i, id[i]);
    }
    printf("}\n");
    return 0;
}
于 2017-05-06T10:28:46.857 回答