chap non-binary trees objects are in different setsand function union merges two sets together private function find is used to find the ultimate root for an object an application using the union/find operations should store set of objectswhere each object is assigned unique index in the range to the indices refer to the corresponding parent pointers in the array class parptrtree creates and initializes the union/find arrayand functions differ and union take array indices as inputs figure illustrates the parent pointer implementation note that the nodes can appear in any order within the arrayand the array can store up to separate trees for examplefigure shows two trees stored in the same array thusa single array can store collection of items distributed among an arbitrary (and changingnumber of disjoint subsets consider the problem of assigning the members of set to disjoint subsets called equivalence classes recall from section that an equivalence relation is reflexivesymmetricand transitive thusif objects and are equivalentand objects and are equivalentwe must be able to recognize that objects and are also equivalent there are many practical uses for disjoint sets and representing equivalences for exampleconsider figure which shows graph of ten nodes labeled through notice that for nodes through ithere is some series of edges that connects any pair of the nodesbut node is disconnected from the rest of the nodes such graph might be used to represent connections such as wires between components on circuit boardor roads between cities we can consider two nodes of the graph to be equivalent if there is path between them thusnodes ahand would be equivalent in figure but is not equivalent to any other subset of equivalent (connectededges in graph is called connected component the goal is to quickly classify the objects into disjoint sets that correspond to the connected components another application for union/find occurs in kruskal' algorithm for computing the minimal cost spanning tree for graph (section the input to the union/find algorithm is typically series of equivalence pairs in the case of the connected components examplethe equivalence pairs would simply be the set of edges in the graph an equivalence pair might say that object is equivalent to object if soc and are placed in the same subset if later equivalence relates and bthen by implication is also equivalent to thusan equivalence pair may cause two subsets to mergeeach of which contains several objects