the disjoint sets class in this we describe an efficient data structure to solve the equivalence problem the data structure is simple to implement each routine requires only few lines of codeand simple array can be used the implementation is also extremely fastrequiring constant average time per operation this data structure is also very interesting from theoretical point of viewbecause its analysis is extremely difficultthe functional form of the worst case is unlike any we have yet seen for the disjoint sets data structurewe will show how it can be implemented with minimal coding effort greatly increase its speedusing just two simple observations analyze the running time of fast implementation see simple application equivalence relations relation is defined on set if for every pair of elements (ab)ab sa is either true or false if is truethen we say that is related to an equivalence relation is relation that satisfies three properties (reflexivea afor all (symmetrica if and only if (transitivea and implies that we will consider several examples the <relationship is not an equivalence relationship although it is reflexivesince <aand transitivesince < and < implies <cit is not symmetricsince < does not imply < electrical connectivitywhere all connections are by metal wiresis an equivalence relation the relation is clearly reflexiveas any component is connected to itself if is electrically connected to bthen must be electrically connected to aso the relation is symmetric finallyif is connected to and is connected to cthen is connected to thus electrical connectivity is an equivalence relation two cities are related if they are in the same country it is easily verified that this is an equivalence relation suppose town is related to if it is possible to travel from to by taking roads this relation is an equivalence relation if all the roads are two-way