The disjoint set class - Data Structures and Problem Solving Using Java - page 921

Note that we have more U.S. pennies than Canadian pennies. The func-
tion α ( M, N ) balances things out, which is why it gives a better bound.
summary
In this chapter we discussed a simple data structure for maintaining disjoint
sets. When the union operation is performed, it does not matter, as far as cor-
rectness is concerned, which set retains its name. A valuable lesson that
should be learned here is that considering the alternatives when a particular
step is not totally specified can be very important. The union step is flexible.
By taking advantage of this flexibility, we can get a much more efficient algo-
rithm.
Path compression is one of the earliest forms of self-adjustment, which
we have used elsewhere (splay trees and skew heaps). Its use here is
extremely interesting from a theoretical point of view because it was one of
the first examples of a simple algorithm with a not-so-simple worst-case
analysis.
key concepts
Ackermann's function A function that grows very quickly. Its inverse is essen-
tially at most 4. (913)
disjoint set class operations The two basic operations needed for disjoint set
manipulation: They are union and find . (895)
disjoint sets Sets having the property that each element appears in only one
set. (894)
equivalence class The equivalence class of an element x in set S is the subset
of S that contains all the elements related to x . (894)
equivalence relation A relation that is reflexive, symmetric, and transitive.
(894)
forest A collection of trees. (906)
Kruskal's algorithm An algorithm used to select edges in increasing cost and
that adds an edge to the tree if it does not create a cycle. (899)
minimum spanning tree A connected subgraph of G that spans all vertices at
minimum total cost. It is a fundamental graph theory problem. (898)
nearest common ancestor problem Given a tree and a list of pairs of nodes in
the tree, find the nearest common ancestor for each pair of nodes. Solu-
tion of this problem is important in graph algorithm and computational
biology applications. (901)