并查集（Union-Find）的路径压缩与按秩合并优化 并查集（Union-Find）是一种用于处理不相交集合合并及查询问题的数据结构。它支持两种操作：查找（Find）某个元素所属的集合，以及合并（Union）两个集合。在基础实现中，通过数组或字典来记录每个元素的父节点，但最坏情况下树可能退化成链，导致操作效率降低。为了优化性能，引入了路径压缩（Path Compression）和按秩合并（Union by Rank）两种技术。 路径压缩（Path Compression） 路径压缩在Find操作中应用，目的是在查找根节点时，将路径上的所有节点直接连接到根节点，从而 flatten 树结构，减少后续操作的路径长度。具体步骤如下： 在Find(x)函数中，递归查找x的根节点。 在递归过程中，将当前节点x的父节点设置为根节点（即更新父指针指向根）。 返回根节点作为x的集合代表。 例如，假设有树结构：根为R，x的父节点为P，P的父节点为R。执行Find(x)时，递归找到R后，在回溯过程中将x的父节点直接设为R（同时P的父节点也可能被设为R）。这样，树的高度降低，后续查询更快。 按秩合并（Union by Rank） 按秩合并在Union操作中应用，通过记录每个树的“秩”（如高度），在合并时总是将较小秩的树合并到较大秩的树下，避免树高度无序增长。步骤包括： 为每个节点初始化一个秩（初始为0）。 当合并两个集合时，比较它们的根节点的秩： 如果秩不同，将较小秩的根节点指向较大秩的根节点。 如果秩相同，任意选择一个根节点作为新根，并将其秩加1（因为合并后高度可能增加）。 这样能控制树的高度，保证操作效率。 结合优化后的操作流程 初始化 ：每个元素自成一个集合，父节点指向自己，秩为0。 Find(x)（带路径压缩） ：递归查找根，并更新路径上节点的父节点。 Union(x, y)（带按秩合并） ：找到x和y的根节点，比较秩，按规则合并。 优化后，每个操作的均摊时间复杂度接近O(α(n))，其中α(n)是反阿克曼函数，增长极慢，在实际应用中可视为常数时间。这种优化使并查集高效适用于网络连通性、图算法等场景。