the disjoint sets class the dynamic equivalence problem given an equivalence relation ~the natural problem is to decidefor any and bif if the relation is stored as two-dimensional array of boolean variablesthenof coursethis can be done in constant time the problem is that the relation is usually not explicitlybut rather implicitlydefined as an examplesuppose the equivalence relation is defined over the five-element set { then there are pairs of elementseach of which is either related or not howeverthe information implies that all pairs are related we would like to be able to infer this quickly the equivalence class of an element is the subset of that contains all the elements that are related to notice that the equivalence classes form partition of severy member of appears in exactly one equivalence class to decide if bwe need only to check whether and are in the same equivalence class this provides our strategy to solve the equivalence problem the input is initially collection of setseach with one element this initial representation is that all relations (except reflexive relationsare false each set has different elementso that si sj this makes the sets disjoint there are two permissible operations the first is findwhich returns the name of the set (that isthe equivalence classcontaining given element the second operation adds relations if we want to add the relation bthen we first see if and are already related this is done by performing finds on both and and checking whether they are in the same equivalence class if they are notthen we apply union this operation merges the two equivalence classes containing and into new equivalence class from set point of viewthe result of is to create new set sk si sj destroying the originals and preserving the disjointness of all the sets the algorithm to do this is frequently known as the disjoint set union/find algorithm for this reason this algorithm is dynamic becauseduring the course of the algorithmthe sets can change via the union operation the algorithm must also operate onlinewhen find is performedit must give an answer before continuing another possibility would be an offline algorithm such an algorithm would be allowed to see the entire sequence of unions and finds the answer it provides for each find must still be consistent with all the unions that were performed up until the findbut the algorithm can give all its answers after it has seen all the questions the difference is similar to taking written exam (which is generally offline--you only have to give the answers before time expiresor an oral exam (which is onlinebecause you must answer the current question before proceeding to the next questionnotice that we do not perform any operations comparing the relative values of elements but merely require knowledge of their location for this reasonwe can assume that all the elements have been numbered sequentially from to and that the numbering can union is (little-usedreserved word in +we use it throughout in describing the union/find algorithmbut when we write codethe member function will be named unionsets