If we replace the loops ‘for’ of the simple version of weighted quick-union (you’ll find it in a previous article) with the following code, we reduce the length of each route passing to the half. The end result of this change is that after a long sequence of operations the trees end up almost level.
Tag Archive: connectivity problem
This program reads from the standard input a sequence of pairs of non-negative integers which are less than N (interpreting the pair [p q] as a “link of the object p to object q”) and displays the pairs that represent those objects which are not yet connected. The program complies with the array ‘id’ to include an entry for each object and applies that id[q] and id[p] are equal if and only if p and q are connected.
If we replace the body of the while loop of the quick-find algorithm (you can find it in a previous article) with the following code we have a program that meets the same specifications as the quick-find algorithm but performs fewer calculations for the act of union, to the expense of more calculations for act of finding. The ‘for’ loop and the ‘if’ operation that follows in this code determine the necessary and sufficient conditions in the array ‘id’ that p and q be linked. The act of union is implemented by the assignment id[i] = j.
This program is a modification of the simple quick-union algorithm (you’ll find it in a previous article). It uses an extra array ‘sz’ to store the number of nodes for each object with id[i] == i in the corresponding “tree”, so the act of union to be able to connect the smaller of the two specified “trees” with the largest, and thus avoid the formation of large paths in “trees”.
Efstathios Chatzikyriakidis 