5820

DISJOINT
Implement the disjoint-set data structure using disjoint-set forests (rooted trees).
With ranked union and with path compression
Your program must support the following functions:
• makeset(x) – creates a set of one element whose data is specified by x.
• find(x) – finds the set (representative) to which the data specified by x belongs.
• union(x, y) – merges the sets containing the data specified by x and y together,
into a single set. After this operation, x and y (as well as the other data that were
also contained in the sets which contained x and y) will belong to the same set.
Input – Output Format
The input consists of multiple lines, each one containing either one or two integers.
The first integer in the line can be 0, 1, 2 or 3, and each one has its own meaning:
• The integer 0 means stop the program.
• The integer 1 stands for the makeset operation. The data for makeset will
be the next integer from the input.
• The integer 2 stands for the find operation. Output the representative of
the set, which contains the next integer from the input. (You are
guaranteed that the input data will be contained in some set).
• The integer 3 stands for the union operation. Merge the sets containing
each of the next two input integers into a single set.
Sample Input
1 25
1 35
1 45
1 55
2 35
2 45
3 35 45
2 35
2 45
2 25
3 25 45
2 25
3 45 25
2 25
2 45
Sample Output (with ranked union and path compression)
35
45
35
35
25
35
35
35