📄️ 15.1 Introduction
So far, we have explored a wide range of data structures, including the "pointer trio" (linked list, tree, and graph) and C++'s built-in STL library. For certain problems, it is necessary not only to utilize multiple data structures but also to nest and integrate them, enabling more complex and efficient operations.
📄️ 15.2 Union-Find
Union-Find (disjoint set) is a data structure used for dynamic connectivity problems. It efficiently connects two points and determines whether two points are connected. Given n nodes, we initialize the parent of each node to itself. To connect nodes i and j, we attach the smaller rank's parent to the larger rank's parent (union by rank). To check if two nodes are connected, we find their ancestors and determine if they are the same, applying path compression to speed up subsequent queries.
📄️ 15.3 Composite Data Structures
This type of problem often uses a hash table or ordered map for auxiliary record-keeping to speed up lookups; paired with arrays or linked lists for continuous data storage to expedite sequential selection or value deletion.
📄️ 15.4 Exercises
Basic Difficulty