引言
目前为止，我们接触了大量的数据结构，包括利用指针实现的三剑客和 C++ 自带的 STL 等。对于一些题目，我们不仅需要利用多个数据结果解决问题，还需要把这些数据结构进行嵌套和联动，进行更为复杂、更为快速的操作。
并查集
并查集 (Union-Fnd) 可以动态地连通两个点，并且可以非常快速地判断两个点是否连通。假设存在 n 个节点，我们先将所有节点的父亲标为自己；每次要连接节点 i 和 j 时，我们可以将 i 的父亲标为 j；每次要查询两个节点是否相连时，我们可以查找 i 和 j 的祖先是否最终为同一个人：
其中 union 操作可以将两个集合连在一起，find 操作可以查找给定节点的祖先，并且如果可以的话，将集合的层数/高度降低。
684. Redundant Connection
因为需要判断是否两个节点被重复连通，所以我们可以使用并查集来解决此类问题。为了加速查找，我们可以使用路径压缩和按秩合并来优化并查集。
复合数据结构
这一类题通常采用 unordered_map 或 map 辅助记录，从而加速寻址；再配上 vector 或者 list 进行数据储存，从而加速连续选址或删除值。
146. LRU Cache
我们采用一个链表 list<pair<int, int>> 来储存信息的 key 和 value，链表的链接顺序即为最近使用的新旧顺序， 最新的信息在链表头节点。 同时我们需要一个嵌套着链表的迭代器的 unordered_map<int, list<pair<int, int>>::iterator> 进行快速搜索，存迭代器的原因是方便调用链表的 splice 函数来直接更新查找成功 (Cache Hit) 时的信息，即把迭代器对应的节点移动为链表的头节点。
练习
1135. Connecting Cities With Minimum Cost
使用并查集，按照 Kruskal’s Algorithm 把这道题再解决一次吧。
380. Insert Delete GetRandom O(1)
设计一个插入、删除和随机取值均为 O(1) 时间复杂度的数据结构。
432. All O`one Data Structure
设计一个 increaseKey，decreaseKey，getMaxKey，getMinKey 均为 O(1) 时间复杂度的数据结构。
716. Max Stack
设计一个支持 push，pop，top，getMax 和 popMax 的 stack。可以用类似 LRU 的方法降低时间复杂度，但是因为想要获得的是最大值，我们应该把 unordered_map 换成哪一种数据结构呢？