CSCI 260 Fall 2026: Lab 2: Union Find: Heuristics for faster performance




To submit through Git:
  1. makefile, .cpp files, .h file for making testappQU
  2. Do not include the executable, or .o files, or the gen program
  3. Do not include your testfile e.g. input.10.25
  4. The program created by the make command implements union-by-rank with path-compression.
  5. The program created by the make command will ask for a file of inputs, and the file will be of the form outlined in Lab 1.
  6. The program will produce no prompts and no outputs except the output produced when debugprint is called, and then the outputs should look as described at the bottom of this page.


Task: You are to modify your Union-Find implementation from Lab 1 to use union-by-rank and path compression. These two algorithmic improvements together consititute the quick-union version of union-find. The executable should be called testappQU ("Quick-Union") to differentiate it from your initial testappUF.


  1. Use git to make the Lab2 directory.
  2. Copy all the .cpp files, .h files, gen, the makefile, and some test files from the Lab1 directory to the Lab2 directory.
  3. cd into the Lab2 directory and change the name of the unionfind.cpp file to unionfindQU.cpp
  4. edit the makefile so that the executable is now called testappQU. If you are using gedit, make sure the setting for tabs (at bottom of window) is not on "use spaces" when you edit your makefile.
    Your new makefile could look like this:

    testappQU: testappUF.o unionfindQU.o
      g++ -o testappQU testappUF.o unionfindQU.o

    testappUF.o: unionfind.h testappUF.cpp
      g++ -c testappUF.cpp

    unionfindQU.o: unionfind.h unionfindQU.cpp
      g++ -c unionfindQU.cpp

    If you are new to makefiles, read up on them a little in your browser; this tutorial may be a good place to start. The thing to remember is that makefiles are very sensitive to the types of white space that are used -- tab must appear before any command (the first line of each couplet above is a list the dependencies; the second line is a command). A makefile is a place to write all the directions for how to make an executable out of code files in the current directory. To invoke the makefile in a given directory, you just invoke the command "make" while in that directory.

    5. Notice that both unionfind.cpp and unionfindQU.cpp use the same header file. That is because they present the same interface. Also, there is no need to change the test program.



How to code the new implementation:

  1. Union-by-Rank

    At initialization, every element is in a singleton set and has rank 0.
    When two sets are merged (unioned), if they are of different rank, the greater rank root is the new root. If rank is a representation of height, does the height need to be updated? No, the height has not changed, so the rank need not be updated. It is no longer necessary to ensure that the name of the set is the set of the first argument in the union (merge) command. When ranks are different, we name the set by the root of the tree with greatest rank, and we make the lower rank tree be a child of the higher rank tree. However, if the rank is a tie, the set associated with the first argument will be the one that is set to the root of the tree, and therefore gives its name to the new, larger, tree.
    When two sets are merged that have the same rank, then the new merged tree will actually have greater height. Its new rank is the old rank plus one; update this in the 'rank' array. By convention, let the first parameter be the new root if they are tied in rank. Use the array "rank" that is in the unionfind.h header file.

  2. Path-compression

    Each time you do a find(i), compress the path from the node i, so that every node on the path from i to i's root now has as its parent node the root of the tree. The find operations performed in the "union" procedure should also involve path-compression.

  3. Debugprint

    Alter "debugprint" so that it first outputs the parent array as is, then does a sequential set print -- i.e., prints out output such as: [3] 0 3 5 7
    [6] 4 6 9
    [8] 1 2 8 10
    That is, it prints out, in increasing order of set-name, the name of the set in square brackets, then all the elements in that set in increasing order. You may have done this as the optional part of Lab 1. If so, the same subroutine (function) will not necessarily work here. Why not? However, if you have programmed your "find" properly to implement path compression, then all that needs to be done in your debugprint is, after you have printed out the contents of the parent array, execute the following loop before you do the set print:
    for (int k=0; k find(k);


    Then you execute the loop that you may have used in Lab1; that is, execute a loop over all the indices from 0 to n-1, and check if parent[i]==i, in which case you would loop through the indices from 0 to n-1 checking to find the elements in the same set as i. Why does it work now, but if you left out the above "find" loop, it wouldn't work?
    Your algorithm should take no more than O(n2) * time to execute a find operation.
    The output it produces should look like this.

    Note that all the files end in "d", for debugprint. This is for testing, and should be left in your executable. However, once you have debugged the programs and if you are interested in comparing testappUF and testappQU for speed, you should remove the "d" from the end of each file; debugprint is not part of our running time calculations of interest.