Thread: Quick Union Algorithm

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

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.

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.