距离面试一个小时越查越慌。前两天一个朋友刚从某电商平台面完Java后端回来跟我吐槽前面项目、八股、Redis缓存那些聊得挺顺结果最后冷不丁甩过来一道算法题——“并查集的路径压缩和按秩合并讲讲原理顺手把实现写出来。”他刷题的时候其实没少碰并查集但那会儿的状态是模板一抄、跑通拉倒真被问到“为什么要这么写”“时间复杂度到底是多少”人直接卡壳了十几秒。这题看着基础其实是Java面试里很典型的一道“低门槛、高区分度”数据结构题代码量不大人人都能写但背后的优化思想、复杂度分析、边界处理甚至面试官的连环追问才是真正拉开差距的地方。并查集Union-Find这套数据结构小到判断两个点是否连通大到Kruskal最小生成树、岛屿数量、等式方程可满足性、冗余连接都是它的主场。而路径压缩和按秩合并这两个优化恰恰是并查集从“能用”变成“又快又稳”的关键所在。这篇文章就把这道面试题彻底掰开揉碎从原理讲到手写实现再从复杂度讲到面试追问和进阶扩展适合正在准备Java后端面试的同学也适合那些刷过题但一直没搞懂“为什么”的人。1. 面试官问这道题到底想听到什么先别急着背模板。得先明白一个事情面试官出这道题表面上是考你会不会写并查集实际上他在考察三个层面的东西第一你有没有真正理解这个数据结构的本质第二你能不能把复杂度分析讲得准确第三你手写代码的时候是不是一个能写出生产级细节的人。1.1 先搞清楚并查集在解决什么问题并查集解决的是动态连通性问题。什么叫动态连通就是有一个集合池里面的元素一开始各自独立然后不断出现“连接两个元素”的操作同时我们需要随时回答“这两个元素现在是不是连通的”。举个生活里的例子。你手机里有好几个微信群一开始每个群只有一个人。后来有些人互相拉群、合并圈子你要判断“A和B是不是在同一个群里”这个判断在每次拉群后都要实时更新。并查集干的就是这件事。它在代码层面的抽象非常朴素用一个数组parentparent[i]表示元素 i 的父节点。初始时每个元素都是自己的父节点也就是parent[i] i每个元素单独成一个集合。当两个元素需要合并时我们把其中一个集合的根节点挂到另一个集合的根节点下面当需要判断连通性时只要看两个元素的根节点是否相同。两个核心操作find(x)找到 x 所在集合的根节点。union(x, y)把 x 和 y 所在的两个不同集合合并成一个。就这么简单。但恰恰因为简单才有很多文章可以做。1.2 为什么Java后端面试偏爱并查集我和很多朋友聊过发现各个大厂面试都喜欢在算法环节塞一道并查集变种题少数直接考模板多数给你一个场景比如“给你一组等式和不等式判断是否冲突”“一堆石头里移除多少个才能让剩余石头不相互连接”你识别出这是并查集之后当场实现。原因有几个。第一并查集代码量小十几行就能写完适合面试这种时间有限的环境。第二它涉及的知识点密度高递归、数组、树形结构、摊还分析、优化策略每一个都能往外延伸追问。第三它和实际工程并不脱节——很多图算法、网络连通性的底层都会用到类似思路作为一个后端开发者这是值得刻在脑子里的基础工具。所以面试官问“路径压缩和按秩合并”表面是问两个优化实际是看你有没有把一个看似玩具的数据结构理解到足够深。这也是为什么这篇文章不只是讲两个优化而是从整个并查集生态去拆解的原因。2. 路径压缩让find一步到位的优化先说不做任何优化时并查集会遇到什么问题。2.1 朴素find为什么会被卡成O(n)最朴素的find写法很直白int find(int x) { while (parent[x] ! x) { x parent[x]; } return x; }沿着 x 一路往上找父节点直到根。这个写法没有技术含量但如果你不停执行这样的合并序列union(1, 2)、union(2, 3)、union(3, 4)…… 而且每次都以一种固定方向挂比如把新节点挂到上一个节点下面那么这棵树就会退化成一条链表。链表意味着什么意味着找深度最大的那个节点的根要一路走到底复杂度O(n)。如果你有n个元素m次操作最坏情况下整体复杂度会恶化到O(n·m)级别。数据量一旦过万就直接肉眼可见地卡住。这也是为什么面试官会让你优化。谁也不会接受一个本来可以用出近似常数的数据结构最后被用成线性甚至更差。2.2 路径压缩的递归写法和迭代写法路径压缩的核心思想特别朴素既然我这次查找 x 的根要把这条路上所有节点都遍历一遍干脆把这条路径上的每一个节点它的父节点直接改成根节点。下次再查任何一个节点一步就能跳到根。最经典的是递归写法int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }find(parent[x])会一直递归到根然后在回溯过程中把路径上每一个节点的parent都设置成根。这叫“路径上所有节点都认祖归宗”。但递归写法和所有递归一样有一个隐患如果树的深度很大比如十万、百万级别递归调用栈会爆。实际工程里如果确定数据规模很大、且没有做按秩合并先保护树的深度可以考虑迭代版本的路径压缩int find(int x) { int root x; while (root ! parent[root]) { root parent[root]; } while (x ! root) { int next parent[x]; parent[x] root; x next; } return root; }第一次循环先找到根第二次循环把这条路径上的所有节点挨个指向根。逻辑也不复杂面试时如果能写出这个版本反而会让面试官觉得你考虑得比一般人周全。注意无论递归还是迭代路径压缩只影响这次find经过的节点没有经过的节点不会动。不要误解成“压缩一次整棵树全扁了”——不是的。2.3 路径压缩的时间复杂度直觉很多面试候选人在这一步会背结论“路径压缩的摊还复杂度是O(α(n))。”但面试官追问一句“为什么”就露馅了。完整的数学证明很复杂但那个结论本身值得理解个八九不离十。路径压缩之后每次find的代价不再跟树高成正比而是跟“这条路径上有多少节点还没直接连到根”有关。被压缩过的节点下次查找就是O(1)而没有被压缩过的节点才会触发一次遍历和压缩。这本质上是一种“按需扁平化”整体摊还下来接近常数级别。有一种常见说法是“单独用路径压缩均摊复杂度大约是O(m log n)m次操作”这在很多资料里会看到。但要说最广为人知的结论还是路径压缩按秩合并一起用复杂度是O(m α(n))其中α是反阿克曼函数增长慢到离谱——对于实际宇宙中任何一种规模的nα(n)都不会超过4。所以你可以直接跟面试官说“实际用它做数亿次操作也可以视为常数级。”3. 按秩合并从源头限制树的高度路径压缩是在find的时候救场属于“事后补救”。但如果你压根不调用某个节点的find它就不会被压缩树照样可能长得又高又瘦。所以还需要第二个优化它发生在union的时候从源头上防止树退化成链。3.1 没有按秩合并链就控制不住想象一个场景你不断地执行union(1, 2)、union(2, 3)、union(3, 4)…… 但目光所及之处你从来不调用find(4)。那么路径压缩永远不会发生在4这条链上整棵树就是一根不折不扣的竖直链。此时查find(1)很快但查find(4)就得走4步查find(1000000)就得走一百步。所以路径压缩不是万能的。你还需要一种策略让每次合并时树的形态尽量矮胖。3.2 按大小合并 vs 按深度合并按秩合并里的“秩”有两种常见理解集合的元素个数或者树的深度。按大小合并把小集合的根挂到大集合的根下面。按深度合并把矮树的根挂到高树的根下面。两种做法最后都能把单独使用时的复杂度稳定在O(log n)。我画一个对比方便你记维度按大小合并按深度合并记录内容集合内元素个数树的深度上界合并策略小集合挂大集合矮树挂高树秩何时增加两个集合大小相等时size翻倍两棵树深度相等时深度1单独使用时高度上限O(log n)O(log n)路径压缩后size依然准确rank变成上界但仍安全为什么单独使用能达到O(log n)?这是因为每次一个节点所在集合的大小/深度至少翻倍而一个元素最多被合并log n次所以每个节点的深度最多O(log n)。这个证明思路面试时可以口头讲出来比直接背结论要让人信服得多。3.3 按秩合并的Java实现细节按深度合并的代码这么写public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } }按大小合并的代码public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } if (size[rootX] size[rootY]) { parent[rootX] rootY; size[rootY] size[rootX]; } else { parent[rootY] rootX; size[rootX] size[rootY]; } }注意几个细节union的第一步一定是先对x和y分别find拿到它们的根节点而不是直接操作原始节点。合并时只有两棵树深度相等才需要对rank加一如果一棵矮树挂到高树下高树的深度并不会改变。另外用了路径压缩之后rank的数值就未必是当前真实的树深了它只是一个“曾经深度”的上界。不过这不影响它作为启发式策略的可靠性因为上界依然能约束树的形态。面试官如果追问这一点你可以很自信地回答说“rank保持的是一个上界而不是精确高度所以不影响正确性非精确反倒给了我们空间不需要在每次路径压缩后更新它。”4. 手写一份可背诵的完整模板面试时基本没有时间现场推理所以一份能背下来的、没有隐患的模板非常重要。下面这个模板我个人用了很久综合了路径压缩和按秩合并还顺手维护了一个集合数量count这个字段很多题都会用到它。4.1 模板代码与设计思路public class UnionFind { private final int[] parent; private final int[] rank; private int count; public UnionFind(int n) { parent new int[n]; rank new int[n]; count n; for (int i 0; i n; i) { parent[i] i; } } public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; } public boolean connected(int x, int y) { return find(x) find(y); } public int getCount() { return count; } }几个设计点说一下parent数组存储父节点初始parent[i] i表示各自为根。rank数组存树的深度上界初始都是0。count维护当前连通分量的数量。每合并成功一次count减一。很多算法题最后的答案就是这个count比如“移除石头使剩余石头不连通”“省份数量”这些题。connected用find(x) find(y)判断这是并查集最常用的查询。4.2 面试时如何把复杂度讲清楚面试官问复杂度最标准、最不容易出错的一种讲法是按“不同优化组合”分层给答案优化组合m次操作总复杂度说明朴素实现O(n·m)最坏情况下树退化成链仅按秩合并O(m log n)每棵树高度限制在log n级别仅路径压缩均摊约O(m log n)大部分节点被扁平化但无高度上限保护路径压缩 按秩合并O(m α(n))α(n) 是反阿克曼函数实际可视为常数最后一句可以加个更通俗的解释“α(n)增长极慢哪怕n是宇宙中的原子数量α(n)也不超过5。所以实际工程中你可以认为这个模板的每次操作是近似O(1)的。”这句话一出来面试官一般都能感觉到你不仅会写还真理解了这个数据结构的威力。注意不要一上来就说“并查集是O(1)”。严格讲只有结合了两种优化才是摊还意义下的“近似常数”如果面试官较真你需要能补上“这是摊还分析不是最坏情况单次O(1)”这句话。5. 面试现场连环追问这些坑我替你踩过了模板会写了复杂度也背熟了但面试官通常不会就此收手。他会沿着你的回答继续往下刨看看你的知识边界在哪里。5.1 高频追问与标准答法这里整理几个我在模拟面试和被真实面试中碰到的追问大家可以对着练。追问1路径压缩会破坏按秩合并用的rank吗不至于破坏正确性。路径压缩之后树变矮了rank记录的深度上界比真实深度大但rank大的树仍然可以认为“曾经更高大”让它做根不会让合并后的树长得不可控。我们把rank看成启发式代价而不是精确深度所以两者结合完全安全。追问2为什么union时两棵深度相等的树合并深度才加1因为矮树挂到高树上整棵树的深度就等于那个高树的深度不会变化。只有两棵树一样深合并后新树深度的确会多一层所以rank自增。追问3你刚写的find是递归版如果数据规模很大递归会爆栈吗会。所以在生产环境或者讨论大规模数据时我更推荐用迭代版本。然后你可以当场把之前写过的迭代版本写一遍会非常加分。追问4并查集还能解决什么实际场景至少说三个Kruskal算法判断图是否形成环在线动态连通性查询处理等式约束的可满足性问题。如果面试官再深入一点你还可以提离线查询中用并查集做逆向删除、在树上做最近公共祖先预处理等。5.2 手写时最容易翻车的细节有些错误平时刷题无所谓面试手写就会被放大。我自己踩过一次之后把最容易出问题的几个点列了出来初始化时忘了写parent[i] i或者写成parent[i] 0后面所有find都会指向0直接乱套。find里递归的是find(parent[x])不是find(x)写错就是无限递归。union里忘了先分别find(x)和find(y)直接拿原节点当根用合并方向全错。重复union两个已经在同一个集合里的节点如果没有先判断rootX rootYcount会被多减。rank的加法时机不对。只在两个rank相等时加不是每次合并都加。数组长度是n循环遍历时边界写成i n数组越界。这些细节都是“笔试不扣分、面试扣印象”的类型。建议面试前把模板默写三遍以上写到不需要动脑的程度。5.3 怎么快速验证写对了面试现场虽然没法跑测试但如果面试官允许你口述验证思路你可以这么说先构造一个5个节点的并查集执行union(0, 1)、union(1, 2)然后调用find(2)观察路径压缩是否把2直接挂到0下面再用connected(0, 2)确认返回true最后看count从5变成4再变成3说明合并逻辑正确。如果你是自己复习我建议写一个小demo用随机操作同时跑朴素版本和优化版本对比每次操作后的连通性结果是否一致顺便打印parent数组观察树的形态变化。这是我最喜欢的自测方式。6. 不止于面试带权并查集与可撤销并查集面试官如果前面聊得高兴通常会抛出一个附加题看看你还有没有扩展知识。如果你主动接住这轮面试基本就稳了。6.1 带权并查集普通并查集只维护“连通性”也就是根是否相同。但有些题目要求维护“相对关系”比如并查集里的两个节点之间的权值差、向量距离、奇偶性。这时候就用带权并查集。它的做法是额外维护一个数组weight[x]表示节点x到其父节点的权值。在find递归时不只是压缩路径还要累加权值在union时需要根据两个节点到根的关系计算出新边权。典型题目有两个一个是“食物链”维护三个物种之间的捕食关系另一个是“奇偶游戏”判断一组区间奇偶性是否矛盾。这类题比裸并查集难不少但背后的模板只需要在find和union里多配一个数组很多Java面试的二轮算法题会从这里出。6.2 可撤销并查集另一个进阶方向是支持“撤销上一次合并操作”。很自然的思路是不做路径压缩因为压缩会破坏历史信息保留按秩合并即可然后用一个栈把每次union修改过的父节点、秩、连通分量数全部记录下来撤销时弹出恢复。这种数据结构在离线分治算法里非常常见比如“动态图连通性”这类问题先离线拿到所有询问再把每一条边在时间轴上的存活区间求出来用线段树分治加可撤销并查集解决。面试时提到它的价值不在于完整写出实现而在于让面试官看到你知道“并查集还有可扩展的方向”。可以说说“如果现场让我写我会用栈保存修改点并禁用路径压缩保证历史可回滚”。这比你默默写个模板要亮眼得多。最后再说一点个人体会我自己的总结是并查集这套东西面试真正的胜负手不在于背模板而在于讲清楚“为什么”。面试官可以容忍你第一次写法不够简洁但很难容忍你说不出路径压缩和按秩合并到底解决了什么问题。准备这道题时建议按这个顺序梳理先想明白动态连通性是什么再手写一遍朴素实现然后分别加两个优化最后把摊还复杂度结论记牢。还有一个很实用的小技巧面试讲复杂度的时候可以顺手画一下树形结构先演示一条链退化再演示压缩后所有节点直接连向根面试官基本立刻知道你懂了。纸上画图有时候比代码更能说明问题。把这篇文章看完之后如果你能不看模板自己从零写出一个带路径压缩和按秩合并的UnionFind并且能把复杂度结论讲得像聊天一样顺那这道题就算真正过关了。后面再做那些连通性相关的算法题你会发现手感完全不一样。