并查集：数据结构与算法的完美结合

并查集（Disjoint Set Union，简称DSU）是一种数据结构，用于管理一组不相交的集合，支持合并集合和查询元素所属集合的操作。

并查集主要包含两个操作：

1. 合并（Union）：将两个不相交的集合合并成一个集合。

2. 查询（Find）：判断两个元素是否属于同一个集合。

并查集的核心思想是使用树结构来表示集合，其中每个节点表示一个元素，树的根节点表示该集合的代表元素。通过将两个集合的根节点连接在一起，即可实现合并操作。

并查集使用一个数组来存储每个元素的父节点，初始时每个元素的父节点指向自身，表示每个元素都是一个独立的集合。当进行合并操作时，将其中一个集合的根节点的父节点指向另一个集合的根节点，即可实现合并。查询操作可以通过递归地查找一个元素的父节点，直到找到根节点，判断两个元素的根节点是否相同来判断它们是否属于同一个集合。

并查集的时间复杂度主要取决于树的高度，因此为了降低树的高度，可以使用路径压缩和按秩合并的优化策略。路径压缩指的是在查询操作中将节点的父节点直接设为根节点，从而减少树的高度。按秩合并指的是将树的高度较小的集合合并到高度较大的集合中，从而保持树的平衡。

并查集在实际应用中广泛用于解决连通性问题，如判断图中的两个节点是否连通、求解连通分量等。它的时间复杂度较低，且操作简单，因此是一种高效的数据结构。

并查集