(BQ) Part 1 book "Introduction to algorithms" has contents: Data structures for disjoint sets, elementary graph algorithms, minimum spanning trees, single source shortest paths, maximum flow, multithreaded algorithms, matrix operations,.and other contents. | 21 Data Structures for Disjoint Sets Some applications involve grouping n distinct elements into a collection of disjoint sets. These applications often need to perform two operations in particular: finding the unique set that contains a given element and uniting two sets. This chapter explores methods for maintaining a data structure that supports these operations. Section describes the operations supported by a disjoint-set data structure and presents a simple application. In Section , we look at a simple linked-list implementation for disjoint sets. Section presents a more efficient representation using rooted trees. The running time using the tree representation is theoretically superlinear, but for all practical purposes it is linear. Section defines and discusses a very quickly growing function and its very slowly growing inverse, which appears in the running time of operations on the tree-based implementation, and then, by a complex amortized analysis, proves an upper bound on the running time that is just barely superlinear. Disjoint-set operations A disjoint-set data structure maintains a collection S D fS1 ; S2 ; : : : ; Sk g of disjoint dynamic sets. We identify each set by a representative, which is some member of the set. In some applications, it doesn’t matter which member is used as the representative; we care only that if we ask for the representative of a dynamic set twice without modifying the set between the requests, we get the same answer both times. Other applications may require a prespecified rule for choosing the representative, such as choosing the smallest member in the set (assuming, of course, that the elements can be ordered). As in the other dynamic-set implementations we have studied, we represent each element of a set by an object. Letting x denote an object, we wish to support the following operations: 562 Chapter 21 Data Structures for Disjoint Sets M AKE -S ET .x/ creates a new set whose only member .
