并查集：并查集是什么？解决“朋友关系”问题的方法

并查集是管理元素分组的高效数据结构，核心解决“合并组”（Union）和“查询是否同组”（Find）问题，适用于快速判断元素是否属于同一集合的场景。其底层以parent数组维护父节点关系，每组视为一棵树，根节点为组代表，初始各元素自成一组。 关键优化是**路径压缩**（查询时压缩路径，使节点直接指向根）和**按秩合并**（小树依附大树，避免树退化为链表），确保操作接近常数时间复杂度。核心方法`find`（查找根节点并压缩路径）和`union`（合并两组，小树根指向大树根）实现高效分组。 应用广泛，如网络连接判断、家族关系查询、最小生成树（Kruskal算法）及等价类问题等，是处理分组场景的简洁强大工具。