1 基本概念
并查集是一类用于管理若干不相交集合的数据结构，核心目标是高效完成“属于哪个集合”“两个元素是否同属一组”“把两组并成一组”等操作。它常被视为处理动态分组问题的基础工具，特别适合集合关系会不断变化、但查询频繁的场景。
1.1 不相交集合
不相交集合指的是任意两个集合之间没有公共元素，元素在某一时刻只会隶属于一个集合。并查集正是围绕这种“分而不交”的结构建立起来的，因此它既能表示分类结果，也能在分类变化时快速更新。
1.1.1 集合划分
集合划分是把一个整体拆分为多个互不重叠的子集，每个元素都被分配到且仅分配到一个子集中。并查集通常维护的就是这种划分状态，随着合并操作执行，原本分开的子集会逐渐减少。
1.1.2 代表元
代表元是每个集合选出的标识元素，用来代表整个集合的身份。两个元素是否属于同一集合，常通过判断它们对应的代表元是否相同来确定。
1.2 并查集的定义
并查集的基本功能可以概括为两项：查找元素所属集合的代表元，以及将两个集合合并为一个集合。由于这两类操作十分高频，数据结构通常会配合一些优化策略，以减少查找链条的长度。
1.2.1 查找操作
查找操作用于定位某个元素所在集合的代表元。它不仅能返回集合标识，还常作为其他操作的前置步骤，是并查集最核心的基础功能之一。
1.2.2 合并操作
合并操作用于把两个原本分离的集合连接起来，使其成为一个更大的集合。合并时通常先找到双方的代表元，再决定将哪一个集合挂到另一个集合下面。
1.2.3 连通性判断
连通性判断是并查集的典型查询形式，常用于判断两个元素是否已经处于同一组中。只要二者的代表元相同，就可以认为它们在当前状态下彼此连通或等价。
1.3 应用场景概览
并查集的应用范围很广，凡是需要反复维护“分组关系”或“连通关系”的问题，往往都能看到它的身影。其优势在于实现直观、查询迅速，适合作为许多算法的底层支持。
1.3.1 动态连通性
动态连通性问题关注的是在边或关系不断加入的情况下，如何及时判断两点是否连通。并查集非常适合这类问题，因为它能够在合并关系后迅速更新连通状态。
1.3.2 图中的连边维护
在图论中，并查集常用来维护边的加入所带来的连通变化。无论是构建连通块，还是判断新增边是否会让两个点落入同一连通分量，都能借助它完成。
1.3.3 分组与聚类问题
一些分组或聚类任务也可以抽象为集合合并问题，例如把有共同特征的对象归入同一类。并查集虽然不负责复杂的聚类计算，但很适合执行“先判断，再合并”的基础管理工作。
2 数据结构表示
并查集最常见的实现方式是借助数组和树形关系来保存集合信息。元素之间并不直接记录“属于哪个集合名称”，而是通过父子指针逐层向上追溯，最终定位到代表元。
2.1 数组实现
数组实现是并查集的经典写法，通常用一个父节点数组来记录每个元素的上级。对于根节点而言，它的父节点一般指向自己，或者以某种特殊标记表示其根身份。
2.1.1 父节点数组
父节点数组用于保存每个元素当前指向的上层节点。通过不断沿着父节点上溯，便可以找到所属集合的根。
2.1.2 根节点判定
根节点是树形结构中的最高节点，也是集合的代表元。判断某个元素是否为根，通常只需看它的父指针是否指向自身，或是否满足预设的根标记条件。
2.1.3 初始状态构建
在初始化阶段，每个元素通常先被视为独立集合，因此父节点会设置为自身。这样一来，结构从“每点一组”的状态开始，后续再通过合并逐步形成更大的集合。
2.2 树形结构模型
并查集在逻辑上可以看作由多棵树组成，每棵树对应一个集合。树中节点的层级关系反映了元素之间的归属路径，而树根则承担集合标识的角色。
2.2.1 每个集合对应一棵树
一个集合内部的所有元素会构成一棵树，树中的任意节点都能沿父链最终走到根。由于根节点唯一，因此集合身份也就唯一。
2.2.2 根节点作为集合标识
根节点不仅是结构上的最高点，也代表整个集合的身份。多个元素如果最终走到同一个根，就说明它们属于同一集合。
2.2.3 多棵树组成森林
当系统中存在多个互不相交的集合时，它们共同形成一片森林。随着合并操作执行，森林中的树数量会逐渐减少。
2.3 结构特征
并查集的树形结构具有一些典型特征，例如层次分明、可沿路径上溯，以及能够记录集合规模等信息。这些特征为后续优化提供了基础。
2.3.1 层次关系
层次关系体现为节点与父节点之间的上下级连接。虽然这种层次并不一定反映真实的逻辑大小，但它决定了查找路径的长度。
2.3.2 路径长度
路径长度是指从某个节点走到根节点需要经过的边数。路径越长，查找时需要访问的节点就越多，因此优化通常围绕缩短路径展开。
2.3.3 集合规模记录
某些实现会额外记录集合规模，以便在合并时做出更合理的连接选择。规模信息既可帮助降低树高，也能在统计问题中直接提供辅助数据。
3 核心操作
并查集的功能主要由查找、合并和查询三类操作组成。其中查找负责定位代表元，合并负责改变集合结构，查询则基于前两者给出关系判断。
3.1 查找
查找用于获取某个元素所在集合的代表元，是整个数据结构中最基础也最常用的操作。它通常需要沿着父指针一层层向上追溯，直到到达根节点。
3.1.1 递归查找
递归查找写法简洁，常通过函数不断调用自身，直到发现当前节点已经是根。返回时还可以顺便修改中间节点的父指向，以改善后续访问效率。
3.1.2 迭代查找
迭代查找则使用循环完成上溯过程，不依赖函数递归栈。它在某些语言或工程环境中更便于控制，也能减少递归带来的额外开销。
3.1.3 路径回溯
路径回溯指的是在找到根节点后，将沿途经过的节点重新连接到更靠近根的位置。这样做的目的是缩短未来再次查找时的路径。
3.2 合并
合并是把两个不同集合连接起来的过程，也是并查集区别于普通查找结构的关键所在。通常只有在确认两个元素原本不属于同一集合时，合并才会真正改变结构。
3.2.1 按根合并
按根合并指的是先找到两个集合各自的代表元，再让其中一个根成为另一个根的子节点。由于集合身份由根决定，因此合并本质上是改变根之间的关系。
3.2.2 合并前的代表元比较
在执行合并前，通常需要比较两个元素的代表元是否相同。如果已经相同，说明它们本来就在同一集合中，此时无需重复合并。
3.2.3 重复合并处理
重复合并是指多次尝试连接已经连通的元素。健壮的实现一般会先判断是否同集合，若已相连则直接返回，以免破坏结构或造成不必要的更新。
3.3 查询
查询操作以集合关系为中心，常用于判断是否同组、获取代表元以及统计当前连通块数量。它通常不直接修改结构，但会依赖查找过程完成判断。
3.3.1 是否同集合
是否同集合是最常见的查询形式，只需比较两个元素的代表元是否一致即可。若代表元相同，则二者属于同一集合。
3.3.2 集合代表元获取
获取集合代表元可以作为身份标记，也可作为后续合并和统计的依据。对于很多算法来说，代表元是连接逻辑与数据结构状态之间的桥梁。
3.3.3 统计连通分量数量
连通分量数量的统计通常通过维护当前根的数量来实现。每次成功合并两个不同集合时，分量总数就会相应减少一。
4 优化策略
并查集之所以高效，关键在于若干经典优化手段的配合使用。最常见的是路径压缩和按秩合并，它们共同降低了树高，使操作趋近于常数级。
4.1 路径压缩
路径压缩会在查找过程中主动缩短树的深度，把访问过的节点尽量直接挂到根节点附近。这样一来，后续访问这些节点时所需的步数会明显减少。
4.1.1 递归压缩
递归压缩通常在递归返回时顺手更新节点父指针，将路径上的节点直接连到根上。它实现简单，且效果通常非常明显。
4.1.2 迭代压缩
迭代压缩可以在循环中完成路径重定向，常见做法是先找到根，再第二次遍历路径并统一修改父指针。该方式更适合需要明确控制流程的实现。
4.1.3 压缩效果分析
路径压缩能显著减少树的平均高度，使重复查询变得更快。随着操作次数增加，结构会逐渐趋于扁平，查找代价也会持续下降。
4.2 按秩合并
按秩合并是一种在合并时尽量保持树平衡的策略。这里的“秩”可以理解为树高，也可以扩展为集合大小等辅助指标。
4.2.1 按树高合并
按树高合并时，通常让较矮的树挂到较高的树下面，避免树高继续快速增长。这样可以减缓查找路径变长的趋势。
4.2.2 按大小合并
按大小合并则将较小集合挂到较大集合下面。由于大集合更不容易被“抬高”，这种策略往往也能保持较好的整体性能。
4.2.3 维护辅助信息
为了支持按秩合并，往往需要额外维护树高、集合大小等信息。合并完成后，这些辅助量也要同步更新，才能保证后续决策准确。
4.3 复杂度优化
并查集的优化目标不仅是减少单次访问时间，也在于让整个操作序列的平均成本尽可能低。经典优化组合后，其总体表现非常接近理想状态。
4.3.1 均摊分析
均摊分析关注的是一连串操作的平均代价，而不是某一次操作的极端情况。对于并查集而言，虽然个别查找可能仍会较慢，但整体平均开销很小。
4.3.2 近似常数时间
在路径压缩与按秩合并共同作用下，单次操作的平均复杂度通常可视为接近常数。严格来说它并非绝对常数，但在实际规模下通常足够高效。
4.3.3 实际性能提升
这些优化不仅改善理论复杂度，也显著提升了工程中的运行速度。对于大量重复查询与合并的任务，优化后的并查集往往更具实用价值。
5 理论分析
并查集的理论基础主要体现在正确性、时间复杂度和空间复杂度三个方面。它之所以被广泛使用，正是因为这三项指标都较为均衡。
5.1 正确性
正确性要求并查集在任意时刻都能准确反映集合划分状态。只要基本不变量保持成立，查询结果就应与真实关系一致。
5.1.1 不变量维护
不变量通常包括“每个节点最终都能追溯到一个根”“根节点自成一类”等内容。只要合并和查找过程不破坏这些条件，结构就是有效的。
5.1.2 合并后的集合一致性
合并后，原本分开的两个集合会共享同一个代表元，从而成为统一整体。此时集合内部的成员关系应保持一致，不应出现一个元素同时归属多个集合的情况。
5.1.3 查询结果可靠性
当代表元计算正确时，同集合判断、分量统计等查询结果也会随之可靠。换言之，查询的正确性依赖于底层结构和操作维护得当。
5.2 时间复杂度
并查集之所以经典，很大程度上是因为它在时间开销上表现优秀。尤其在采用优化策略后，查找和合并都能保持很低的平均成本。
5.2.1 单次查找复杂度
单次查找的复杂度与树高有关。若树较深，查找会更慢；若经过路径压缩，实际访问步骤通常会大幅减少。
5.2.2 单次合并复杂度
单次合并通常由两次查找和一次链接组成，因此其成本主要受查找过程影响。若辅助策略得当，合并也可保持很高效率。
5.2.3 总体均摊复杂度
对于大量混合操作序列，并查集的总体均摊复杂度非常低。也正因为如此，它常被用于需要长时间在线维护关系的算法场景。
5.3 空间复杂度
并查集在空间方面通常较为节省，主要依赖若干线性数组来保存父节点和辅助信息。相比许多复杂图结构，它的存储需求较为稳定。
5.3.1 存储开销
基础存储开销主要来自父节点数组，通常与节点数量成正比。若只维护最基本信息，额外空间需求并不高。
5.3.2 辅助数组开销
若采用按秩合并、规模统计或带权维护，还需要额外数组保存相应信息。这些开销一般也保持线性增长，不会突然膨胀。
5.3.3 大规模数据下的内存表现
在大规模数据下，并查集通常仍能保持较好的内存表现。只要数组设计合理，它往往适合作为大样本问题中的基础结构。
6 典型应用
并查集在图论、关系维护和工程实现中都有大量应用。它的价值不在于表达复杂语义，而在于高效地维护“是否连在一起”这类核心信息。
6.1 图论问题
在图论中，并查集最常见的用途是处理连通性和边的增量维护。许多看似复杂的图问题，都可以先降解为集合合并问题。
6.1.1 连通分量维护
连通分量维护指的是持续记录图中各部分是否已经连在一起。每加入一条边，就可能使两个原本独立的分量合并为一个。
6.1.2 最小生成树
在最小生成树相关算法中，并查集常用于判断新增边是否会形成环。它能快速识别两端点是否已经连通，从而辅助边的选择过程。
6.1.3 环检测
环检测可以通过判断某条边连接的两个点是否已在同一集合中来完成。若已经连通，再加入这条边就可能形成环。
6.2 动态关系维护
并查集也常用于处理人与对象之间的动态关系，例如朋友关系、分组状态或实时连通查询。它能以较低成本持续更新关系网。
6.2.1 朋友关系判定
在朋友关系判定中，若两个人通过若干已知关系间接相连，就可视作处于同一关系集合。并查集可快速回答“是否属于同一朋友圈”之类的问题。
6.2.2 分组合并
分组合并问题中，系统会不断把具有某种关联的对象合并到同组。并查集非常适合这种逐步扩展的分组过程。
6.2.3 在线连通查询
在线连通查询要求在操作持续到来时立即返回答案。并查集能够在不预处理完整结构的情况下高效回应，因此十分实用。
6.3 算法竞赛与工程实现
并查集因代码短、逻辑稳、性能好，长期是算法竞赛中的常客，也常被工程实现直接采用。它的模板化程度高，容易快速部署到具体问题中。
6.3.1 模板化代码
并查集的核心代码往往可以写成通用模板，只需替换节点规模和辅助信息即可复用。正因如此，它常被视为基础算法库中的固定组件。
6.3.2 数据范围适配
根据数据范围的不同，数组大小、编号方式和辅助变量都需要相应调整。对于较大规模输入，初始化和内存规划尤其重要。
6.3.3 与其他结构的配合
并查集常与排序、图遍历、线段树等结构配合使用。它负责维护关系状态，其他结构则处理顺序、区间或路径等更复杂的信息。
7 扩展与变体
除了最基本的集合维护并查集外，还存在多种扩展版本，用于处理关系值、历史回退或与其他算法协同的问题。这些变体延伸了并查集的适用范围。
7.1 带权并查集
带权并查集在父指针之外，还会维护节点之间的相对关系值。它适合处理距离、差值或某种可累计约束的问题。
7.1.1 维护节点间关系值
这类结构不仅记录“谁的父亲是谁”，还记录当前节点到父节点之间的权值关系。通过沿路径累积，就能得到任意两点间的相对信息。
7.1.2 距离关系处理
距离关系处理中，节点之间的距离可以在合并和查找时同步更新。它常用于需要比较两点间间隔或差异的场景。
7.1.3 差分信息维护
差分信息维护关注的是元素之间的数值差，而非单纯的连通关系。带权并查集能够把这种差值约束自然嵌入树结构中。
7.2 可回滚并查集
可回滚并查集支持撤销部分合并操作，使结构回到此前的某个状态。它常见于需要离线处理、分治回溯或时间旅行式查询的问题。
7.2.1 历史状态保存
为了实现回滚，系统通常要保存关键操作前的历史信息。这样在需要撤销时，才能恢复到旧的父指针和辅助数据。
7.2.2 撤销合并操作
撤销合并意味着把刚刚连接起来的两个集合重新拆开。与普通并查集不同，这类结构需要严格记录合并前后的变化。
7.2.3 离线查询支持
可回滚机制常用于离线查询，因为查询顺序和合并顺序可以在预处理阶段重新组织。借助这种方式，某些动态问题可被转化为可管理的分治过程。
7.3 并查集与其他结构结合
并查集自身擅长维护集合关系，但在复杂问题中往往需要与其他结构联动。通过组合使用，可以解决更丰富的约束与查询任务。
7.3.1 与线段树结合
与线段树结合时，并查集常负责维护区间相关的连通关系，而线段树则负责管理时间区间或位置区间上的变化。两者配合能支持更复杂的离线处理。
7.3.2 与图算法结合
在图算法中，并查集常作为辅助判定工具，用来帮助筛边、判断连通或维护组件状态。它不会取代图算法本身，而是提供高效的关系基础。
7.3.3 与搜索策略结合
与搜索策略结合时，并查集可以减少重复判断，避免对已知连通关系进行多余搜索。这样既能提高效率，也能简化状态管理。
8 实现细节
并查集虽然概念简单，但实现时仍有不少细节需要注意。初始化是否正确、父指针是否更新到位，都会直接影响结果。
8.1 初始化
初始化阶段决定了数据结构的起点状态，通常要保证每个元素都处于可独立识别的初始集合中。若这一步出错，后续所有操作都可能被连带影响。
8.1.1 节点编号
节点编号需要统一，常见做法是采用从 0 或 1 开始的连续编号。只要全局保持一致，就能减少访问混乱。
8.1.2 父指针设置
初始化时，父指针一般设置为指向自身，表示每个元素都是单独的根。这样可以方便地从最简单状态开始构建集合。
8.1.3 辅助数组初始化
若结构中还包含树高、规模或权值等辅助数组，也必须在初始化时一并清零或赋初值。否则合并时可能出现错误判断。
8.2 常见写法
并查集实现通常有递归版、迭代版和按规模合并版等常见模板。不同写法各有风格，但核心思想基本一致。
8.2.1 递归版模板
递归版模板最为常见，通常以简短函数完成查找与路径压缩。它代码紧凑，便于快速记忆和使用。
8.2.2 迭代版模板
迭代版模板减少了递归调用，更适合强调过程控制或避免栈深风险的场景。它的思路与递归版一致，只是写法更显式。
8.2.3 规模合并模板
规模合并模板会在合并时比较两棵树的大小，再决定连接方向。该做法常与路径压缩一同使用，以保持较低树高。
8.3 常见错误
并查集的错误往往不是概念问题，而是实现细节上的疏漏。由于结构依赖父指针链条，任何一处更新不当都可能造成连锁偏差。
8.3.1 忘记压缩路径
忘记压缩路径会让树逐渐变深，从而降低查询效率。虽然不一定立刻出错，但在大数据下很容易导致性能退化。
8.3.2 父节点更新错误
父节点更新错误会直接破坏集合结构，导致代表元判断失真。轻则查询结果不准，重则出现死循环或非法访问。
8.3.3 越界与重复初始化问题
越界通常发生在编号范围和数组大小不匹配时，而重复初始化则可能覆盖已有状态。两类问题都属于常见工程失误，需要在实现时格外留意。
</INTERNAL_LINK_CANDIDATES> 并查集（用于维护不相交集合的合并与查询的数据结构） 路径压缩（查找时将路径上的节点直接连向根的优化方法） 按秩合并（按树高或规模决定合并方向的优化策略） 动态连通性（在边不断加入时维护图连通状态的问题） 连通分量（图中彼此可达的节点集合） 最小生成树（连接所有顶点且总权重最小的生成树） 环检测（判断图中是否出现回路） 带权并查集（维护节点间差值或距离关系的并查集变体） 可回滚并查集（支持撤销合并操作的并查集变体） 线段树（用于区间查询与修改的树形数据结构） 图算法（处理图结构问题的一类算法统称） 搜索策略（用于遍历或查找状态的算法方法）