并查集

基本概念

将两个集合合并

• 例如问两个元素是否在一个集合中

原理

用树来表示，根节点是集合编号（区分集合） 每个节点记录父节点，每次查找父节点直到到头

查找过后进行优化，将找得到根节点的查找过程经过的子节点都直接连向根节点，使查找更加快捷，称为 路程压缩

合并则是将另一根节点作为子节点指向当前集合的根节点

具体实现

并查集更多的是一种思想，即路径压缩的思想

维护新元素

• 可以维护一个新数组来实现更多信息的维护
• 代码