Quick Union Algorithm

Hi everyody!
So, my teacher gave me this program that implements the normal quick find but I don't seem to understand those two for lines in the program... what do they do? why do they have a ";" at the end?

Code:

---

#include <stdio.h>#define N 10000
main()
{
        int i, j, p, q, id[N];
        for(i=0; i<N; i++)
          id[i] = i;
        printf("Input pair p q:  ");
    while (scanf("%d %d", &p, &q) ==2)
        {
                  for (i = p; i!= id[i]; i = id[i]);
                  for (j = q; j!= id[j]; j = id[j]);
                  if (i == j)
            printf("pair %d %d already connected\n", p,q);
                  else
          {
                id[i] = j;
                        printf("pair %d %d not yet connected\n", p, q);
          }
          printf("Input pair p q:  ");
        }
    system("pause");
}

---

Thanks everybody :)

They have a ; at the end because there is no block of code executed in the loop. So the purpose of this is simply to set i and j.

You need to initialize id[], since otherwise it is possible that some element could coincidentally contain a value that will screw your algo up. Even worse, those values will certainly lead you out of bounds in the first for().

Code:

---

int id[N] = { 0 };

---

Will zero it out. That means that during the first iteration of the while() loop, at the first for():

Code:

---

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

---

i will end up == 0 no matter what.

I don't think you have any choice but zero here, since the value at id[i] is then used to set i in that loop (this is also why you must initialize all of id[] to something less than N).

Quote:

---

Originally Posted by MK27

Code:

---

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

---

i will end up == 0 no matter what.

---

Not sure how you make that conclusion.
Try it with:

Code:

---

i = 3;
id = {4, 3, 2, 0, 2};

---

You should get i going through these values 3,0,4,2,2 and then ending on 2. See how it works now?

Damn, it made me use code tags.

Quote:

---

Originally Posted by iMalc

Not sure how you make that conclusion.
Try it with:

Code:

---

i = 3;
id = {4, 3, 2, 0, 2};

---

---

In context, I said pretty clearly that only WRT id[] being initialized to zero:

Quote:

---

Originally Posted by MK27

Code:

---

int id[N] = { 0 };

---

Will zero it out. That means that during the first iteration of the while() loop, at the first for():

Code:

---

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

---

---

So, like I said, i must end up as zero there on the first iteration. And it looks to me like id does have to be zero'd first for that algo to work consistently.