For this assignment you are going to do some code with disjoint sets. As with all the assignments, you can write this in whatever language you want, but I have to be able to compile and run it under Linux on the lab machines. What you turn in will be graded for correctness and speed. It might also be used in a future assignment so keep that in mind and try to build flexible and robust data structures. You will use this data structure to solve the following problem. You might also use some other data structures to go along with it, but you don't have to write those if you can find a good library for them. You are required to write any heaps or priority queues that you use for this assignment.
Since the disjoint data set stuff is fairly simple and we haven't covered graphs yet, this assignment is going to be fairly easy. This is going to be a rather simple model of corporations in a mock economy. In this economy there are two operations. You can have new companies form and companies can be acquired in mergers. As an economic historian, you are interested in what conglomerate a particular company has become part of at some later point in time. For input you will be given names of new companies and told when companies are merging. The merger could be specified for any subentity inside of either company. You will occasionally be asked for information about whether two companies are part of the same conglomerate.
The interface for this program will be all text. You will read from standard input and write to standard output. Each line of input will have a command that you have to process. The meaning of each command and what you must print for it, if anything, is given below.
The input will take the following format.
NEW name
This will create a new company with the given name.
MERGE name1 name2
Here the conglomerates that include these two companies are to be merged together.
SAME name1 name2
This will print the two names separated by a comma followed by either " - unrelated" or " - together". So you might have a line like "Coke, Peps - unrelated".
Here is sample input: