# Thread: Quick Union Algorithm

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

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

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

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

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.

Popular pages Recent additions