Hello,

I read Algorithms in C (3rd edition) by R.Sedgewick and I am a bit confused about the very first algorithm in the book, which aims to store connections between different nodes - so if the input for the program is 1 2 it means that first node is connected to the second. Here is the algorithm code:

Code:

#include <stdio.h>
#define N 10000
main() {
int i, p, q, t, id[N];
//init of the array
for (i = 0; i < N; i++) id[i] = i;
while (scanf(" %d %d", &p, &q) == 2) {
//find operation
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
//union operation
id[i] = j;
/* let's print out connection table */
for (i = 0; i < 10; i++)
printf("%d-",id[i] );
printf("\n");
fflush(stdout);
}
}

Here is the example input and output for the case when the input pairs pairs come in order 1-2 2-3 and so forth:

0 1

1-1-2-3-4-5-6-7-8-9-

1 2

1-2-2-3-4-5-6-7-8-9-

2 3

1-2-3-3-4-5-6-7-8-9-

3 4

1-2-3-4-4-5-6-7-8-9-

4 5

1-2-3-4-5-5-6-7-8-9-

5 6

1-2-3-4-5-6-6-7-8-9-

6 7

1-2-3-4-5-6-7-7-8-9-

7 8

1-2-3-4-5-6-7-8-8-9-

8 9

1-2-3-4-5-6-7-8-9-9-

The author claims that for the input just provided above we get a straight line with N (9 in this case) pointing to N-1 which points to N-2 etc and here I agree. Then he claims that to execute the find operattion for object N the program has to follow N-1 pointers - here I don't agree. When N==9 the loop
Code:

for (i = p; i != id[i]; i = id[i]) ;

will get straight into the correct pointer and we terminate at the first check of . Do you agree?

Next. he says:

Now suppose that the remainder of the pairs all connect N to some other object. The find operation for each of these pairs involves at least (N-1) pointers. The grand total for the M find operations for this sequence of input pairs is certainly greater than MN/2.

First of all I don't get what he understands by "remainder of the all pairs" but if they are those >N then I still don't get why the find operation for them would take N-1 pointers. Let's take N+1 as an exmaple here. This is 10 in our case and it was id[10] = 10 (initialized by the starup for loop) so where the N-1 comes from? :|

Thanks