The Disjoint-Set data structure and its performance

Abstract

Disjoint-set data structure is a data structure that stores a collection of disjoint (nonoverlapping) sets.The Disjoint-Set data structures (also called Union-Find) is a very elegant and efficient way of analyzing connectivity in a graph. It makes use of the concept of dynamic programming to reach its running speed. Using splitting or halving with union by size or by rank, or using path compression, we can reduce the running time of these operations.