be determined easily by some hashing scheme thusinitially we have si {ifor through our second observation is that the name of the set returned by find is actually fairly arbitrary all that really matters is that find( )==find(bis true if and only if and are in the same set these operations are important in many graph theory problems and also in compilers which process equivalence (or typedeclarations we will see an application later there are two strategies to solve this problem one ensures that the find instruction can be executed in constant worst-case timeand the other ensures that the union instruction can be executed in constant worst-case time it has recently been shown that both cannot be done simultaneously in constant worst-case time we will now briefly discuss the first approach for the find operation to be fastwe could maintainin an arraythe name of the equivalence class for each element then find is just simple ( lookup suppose we want to perform union( ,bsuppose that is in equivalence class and is in equivalence class then we scan down the arraychanging all is to unfortunatelythis scan takes (nthusa sequence of unions (the maximumsince then everything is in one setwould take ( time if there are ( find operationsthis performance is finesince the total running time would then amount to ( for each union or find operation over the course of the algorithm if there are fewer findsthis bound is not acceptable one idea is to keep all the elements that are in the same equivalence class in linked list this saves time when updatingbecause we do not have to search through the entire array this by itself does not reduce the asymptotic running timebecause it is still possible to perform ( equivalence class updates over the course of the algorithm if we also keep track of the size of each equivalence classand when performing unions we change the name of the smaller equivalence class to the largerthen the total time spent for merges is ( log nthe reason for this is that each element can have its equivalence class changed at most log timessince every time its class is changedits new equivalence class is at least twice as large as its old using this strategyany sequence of finds and up to unions takes at most ( log ntime in the remainder of this we will examine solution to the union/find problem that makes unions easy but finds hard even sothe running time for any sequence of at most finds and up to unions will be only little more than ( basic data structure recall that the problem does not require that find operation return any specific namejust that finds on two elements return the same answer if and only if they are in the same set one idea might be to use tree to represent each setsince each element in tree has the same root thusthe root can be used to name the set we will represent each set by tree (recall that collection of trees is known as forest initiallyeach set contains one element the trees we will use are not necessarily binary treesbut their representation is this reflects the fact that array indices start at