并查集（Disjoint Set Union, DSU）

并查集（Disjoint Set Union, DSU）是一种非常有用的数据结构，主要用来处理一些不相交集合的合并及查询问题。听起来很抽象，但其实核心就两个操作： find：查找一个元素属于哪个集合（通常通过返回该集合的代表元素，也就是根节点）。 union：将两个元素所在的集合合并成一个集合。 为了让find操作更快，我们通常会加上一个“路径压缩”的优化。为了让合并后的树结构更平衡，会加上“按秩合并”或“按大小合并”的优化。 10.2 一维并查集的应用算法设计 10.2.1 以图判树...