the disjoint sets class { { { { { { { { { { { { figure wall between squares and is randomly selected in figure this wall is knocked downbecause and are not already connectedtheir sets are merged { figure eventually walls are knocked downall elements are in the same set summary we have seen very simple data structure to maintain disjoint sets when the union operation is performedit does not matteras far as correctness is concernedwhich set retains its name valuable lesson that should be learned here is that it can be very important to consider the alternatives when particular step is not totally specified the union step is flexibleby taking advantage of thiswe are able to get much more efficient algorithm path compression is one of the earliest forms of self-adjustmentwhich we have seen elsewhere (splay treesskew heapsits use is extremely interestingespecially from theoretical point of viewbecause it was one of the first examples of simple algorithm with not-so-simple worst-case analysis