# 简介

并查集是计算机中的集合算法。不同集合间无交集，可用于解决元素分组问题。

在每个集合中指定一个代表元素，代表该集合。

该算法有两种基本操作：

合并（Union） 把两个不相交的集合合并成一个集合

查询（Find） 查询两个元素是否在同一个集合中。

利用树构成一个集合。递归查询节点的父节点便可获得根节点。

# 实现

设立一个数组，储存每个元素的父元素。

如第 1 个节点的父节点为 fa[1]

# 优化

# 路径压缩

合并集合时，每个节点只储存根节点。即，树的深度为 2。

# 秩的压缩