In this project you will use a disjoint set to keep track of connected cities.
The input file attached(cities_map) has a list of cities. The file consists of a set of cities in rows and columns. Cities in a row are adjacent, as are cities in a column.
We want to randomly form connections between adjacent cities until all cities are connected. To do this, use a disjoint set object. Number the cities as they are read. Create a disjoint set object so that there is one disjoint set per city. Now, randomly selected a pair of cities. If they are adjacent, see if they are connected. To do this, see if they are in the same set. If they are not connected, then union them in the set, and create a vertical or horizontal connection between them.
When all cities are connected, print out your list of cities to show which cities have been connected.
You MUST use the disjoint set object from this given website:
[url removed, login to view]~weiss/dsaa_c++/code/
(see attachment for files [url removed, login to view] and DisjSets.h).
You should submit the source files and all the necessary files to execute the program.
It should be compilable on apache servers version 3.03