应用于配对序列时有关快速 union 算法的困惑 : 1-2, 2-3,3-4

Question

据我的理解，在快速 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);

}
} 

Answer 1

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

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

但是，链接将按照描述的相反方向进行。