并查集 快速寻找通路

并查集（Disjoint Set）是一种用于处理不相交集合的数据结构。它主要支持两种操作：合并（Union）和查找（Find）。

并查集的主要应用之一是快速寻找通路。在一个图中，我们可能需要判断两个节点是否属于同一个连通分量，即是否存在一条路径可以从一个节点到达另一个节点。并查集可以高效地解决这个问题。

并查集的基本思想是使用树结构来表示集合，其中每个节点表示一个元素，树的根节点表示该集合的代表元素。初始时，每个元素都是一个独立的集合，即每个元素的根节点都是自己。

合并操作将两个集合合并为一个集合，即将两个集合的根节点连接起来。查找操作用于确定一个元素所属的集合，即找到该元素所在树的根节点。

为了提高效率，可以使用路径压缩和按秩合并两种优化策略。路径压缩是在进行查找操作时，将路径上的所有节点直接连接到根节点，以减少后续查找的时间。按秩合并是在进行合并操作时，将较小的树连接到较大的树上，以保持树的平衡性。