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
Code:
i != id[i]
. 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