3. When we use Kruskal's algorithm to solve the minimum spanning tree problem, an edge is added if it does not create a cycle. We use disjoint sets data structure to determine whether two vertices below to a same set. In disjoint sets, the uptrees are used to represent sets in the union-find algorithm. And, uptrees can be stored in two n-element arrays, where n is the number of items. The up array stores the parent of each node. The weight array stores the number of items in a set if the node is the root of a set. The weight array is ignored in this problem. (20%)
1 2 3 4 5 6 7 8 9
up 6 6 -1 3 8 -1 6 3 -1
weight
(a) Draw the uptrees represented by the data in the up array in the above table.