Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 21

The authors discuss about disjoint set data structures in this chapter which maintains a collection of disjoint dynamic sets. Each set is identified by a respresentative, which is some member of the set.

The authors define three operations, MAKE-SET, FIND-SET and UNION on disjoint set data structures. The authors then provide an application for the disjoint set data structures in determining the connected components of an undirected graph.

The authors then provide an implementation of disjoint set data structure by a linked list. The authors then discuss time complexity of each disjoint set data structure operation with this implementation. The authors then provide an implementation of disjoint set data structure by rooted trees and discuss the pseudocode and time complexity of each disjoint set data structure operation with this implementation.