📄️ 15.1 引言
目前为止,我们接触了大量的数据结构,包括利用指针实现的三剑客和 C++ 自带的 STL 等。对于一些题目,我们不仅需要利用多个数据结果解决问题,还需要把这些数据结构进行嵌套和联动,进行更为复杂、更为快速的操作。
📄️ 15.2 并查集
并查集(union-find, disjoint set)可以动态地连通两个点,并且可以非常快速地判断两个点是否连通。假设存在 n 个节点,我们先将所有节点的父节点标为自己;每次要连接节点 i 和 j 时,我们可以将秩较小一方的父节点标为另一方(按秩合并);每次要查询两个节点是否相连时,我们可以查找 i 和 j 的祖先是否最终为同一个人,并减少祖先层级(路径压缩)。
📄️ 15.3 复合数据结构
这一类题通常采用哈希表或有序表辅助记录,从而加速寻址;再配上数组或者链表进行连续的数据储存,从而加速连续选址或删除值。
📄️ 15.4 练习
基础难度