并查集是一种树型的数据结构，用于处理一些不相交集（Disjoint Sets）的合并及查询问题。不相交集，顾名思义，就是交集为空集的一些集合。比如集合 {1,3,5} 和集合 {2,4,6} 就是不相交集。 {2,3,5} 和 {1,3,5} 就不是，因为他们的交集不是空集。 主要操作 查找 找到一个结点的祖先 合并 将两个集合合并 用途 判断连通性、最小生成树, Kruskal 算法、最近公共祖先（Least Common Ancestors, LCA）等 示例 洛谷p1551