并查集用森林维护集合归属，f[x] 记 x 的父亲，根节点的父亲是自身。两种优化：路径压缩（查询时把路径上的点直接挂到根，常用）与启发式合并（小树并大树，带权并查集中常用）。 基本并查集（路径压缩） 1234567891011121314cons...

基础知识 并查集是一种树形数据结构。在全国青少年信息学奥林匹克系列竞赛大纲中难度为 6，是提高级中学习的数据结构。 并查集的基本操作： 查询一个元素在哪个集合。 合并两个集合。 使用一个森林来存储并查集，一个元素是一个结点，每棵树是一个集合。用...