并查集的路径压缩：并查集优化，让查找更快
并查集用于解决集合合并与元素归属问题（如连通性判断）。核心操作是`find`（查找根节点）和`union`（合并集合），基础版通过`parent`数组记录父节点实现，但长链结构会导致`find`效率极低。为优化，引入**路径压缩**：在`find`过程中，将路径上所有节点直接指向根节点，使树结构扁平化，查找效率接近O(1)。路径压缩通过递归或迭代实现，将长链转化为“一步到位”的短路径。结合按秩合并等优化，可高效处理大规模集合问题，成为解决连通性、归属判断的核心工具。
阅读全文并查集：并查集是什么？解决“朋友关系”问题的方法
并查集是管理元素分组的高效数据结构，核心解决“合并组”（Union）和“查询是否同组”（Find）问题，适用于快速判断元素是否属于同一集合的场景。其底层以parent数组维护父节点关系，每组视为一棵树，根节点为组代表，初始各元素自成一组。 关键优化是**路径压缩**（查询时压缩路径，使节点直接指向根）和**按秩合并**（小树依附大树，避免树退化为链表），确保操作接近常数时间复杂度。核心方法`find`（查找根节点并压缩路径）和`union`（合并两组，小树根指向大树根）实现高效分组。 应用广泛，如网络连接判断、家族关系查询、最小生成树（Kruskal算法）及等价类问题等，是处理分组场景的简洁强大工具。
阅读全文