并查集（Union-Find）的路径压缩与按秩合并优化 并查集（Union-Find）是一种用于处理不相交集合合并与查询问题的数据结构。它支持两种操作：查找（Find）某个元素所属的集合代表元素，以及合并（Union）两个集合。为了提高效率，常采用路径压缩（Path Compression）和按秩合并（Union by Rank）两种优化策略。 基本概念与初始化 并查集维护一个数组 parent[] ，其中 parent[i] 表示元素 i 的父节点。初始时，每个元素自成一个集合，因此 parent[i] = i （即每个元素都是自己的根节点）。 例如，对于元素集合 {0, 1, 2, 3}，初始化后 parent = [0, 1, 2, 3] 。 查找操作（Find）的优化：路径压缩 查找操作的目标是找到元素所在集合的根节点（即根节点的父节点是自身）。 未优化的查找需要沿着父链向上遍历，最坏情况下时间复杂度为 O(n)。 路径压缩优化 ：在查找过程中，将路径上的所有节点的父节点直接指向根节点，使路径变平，加速后续查找。 步骤： 递归找到根节点 root 。 将路径上每个节点的父节点设置为 root 。 返回 root 。 示例：查找元素 3 的根节点，若路径为 3 → 2 → 1 → 0（0 是根节点），则压缩后 3 和 2 的父节点直接变为 0。 合并操作（Union）的优化：按秩合并 合并操作将两个集合合并为一个。未优化的合并可能使树退化为链，导致查找效率下降。 按秩合并优化 ：总将较小的树（以秩衡量高度）合并到较大的树下，避免树过高。 维护一个秩数组 rank[] ，初始时每个节点的秩为 0（单节点树高度为 0）。 步骤： 找到两个元素的根节点 rootX 和 rootY 。 若 rank[rootX] > rank[rootY] ，将 rootY 的父节点设为 rootX 。 若 rank[rootX] < rank[rootY] ，将 rootX 的父节点设为 rootY 。 若秩相等，任选一个作为根，并将其秩加 1（因合并后高度可能增加）。 示例：合并集合（根节点为 0）和集合（根节点为 1），若 rank[0] = 1 ， rank[1] = 0 ，则将 1 合并到 0 下，秩不增加；若秩均为 1，则合并后新根秩变为 2。 优化后的时间复杂度 结合路径压缩和按秩合并，每次操作的平均时间复杂度接近 O(α(n))，其中 α(n) 是反阿克曼函数，增长极慢，可视为常数。 应用场景 并查集常用于网络连通性判断、最小生成树算法（如 Kruskal）、动态等价类问题等。 通过这两种优化，并查集在实践中的效率显著提升，适用于大规模数据处理。