当前位置：首页 > news >正文

面试官问我LCA，我讲了倍增和Tarjan还不够，他让我用并查集再实现一遍？

news 2026/6/12 4:32:21

当面试官要求用并查集实现LCA：一种颠覆常规的解法探索

面试官的问题总是能让人措手不及。就在上周，我经历了一场令人难忘的技术面试——当我对LCA（最近公共祖先）问题侃侃而谈，从朴素算法讲到倍增和Tarjan，正准备松一口气时，面试官突然抛出一个问题："能否用并查集的思想，在不预处理深度的情况下，实时查询LCA？"那一刻，我意识到常规的算法准备远远不够。

1. 重新审视LCA问题的本质

LCA问题看似简单，却蕴含着丰富的算法思想。传统解法通常分为两类：在线算法（如倍增）和离线算法（如Tarjan）。但面试官的问题直指一个更深层的思考——我们是否能够跳出这些常规框架，用完全不同的数据结构解决同一问题？

并查集（Union-Find）通常用于处理不相交集合的合并与查询，它与树结构的LCA问题似乎风马牛不相及。但仔细思考会发现，两者都涉及连通性管理这一核心概念。在Tarjan算法中，并查集用于标记已访问节点的集合，而我们需要更进一步——直接利用并查集维护祖先关系。

关键突破点：在DFS遍历过程中，通过并查集动态维护节点的"当前祖先"，利用回溯时的合并操作记录LCA信息。

2. 基于并查集的LCA算法设计

2.1 算法核心思想

这种方法的精妙之处在于将并查集的路径压缩特性与树的后序遍历相结合。具体步骤如下：

初始化：为每个节点创建独立的并查集，祖先指向自己
DFS遍历：对树进行深度优先搜索，访问完所有子节点后再处理当前节点
合并操作：回溯时将子节点的集合与当前节点合并
查询处理：当两个节点都被访问时，它们的LCA即为其中一个节点所在集合的代表元素

class UnionFind: def __init__(self, n): self.parent = list(range(n+1)) # 节点从1开始编号 def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x != root_y: self.parent[root_y] = root_x def tarjan_lca(u, queries, adj, uf, visited, results): visited[u] = True for v in adj[u]: if not visited[v]: tarjan_lca(v, queries, adj, uf, visited, results) uf.union(u, v) # 关键步骤：将子节点合并到当前节点 # 处理所有与u相关的查询 for (v, idx) in queries.get(u, []): if visited[v]: lca = uf.find(v) results[idx] = lca

2.2 与经典Tarjan算法的对比

虽然这种方法也使用并查集，但与标准Tarjan算法有本质区别：

特性	经典Tarjan	并查集LCA
预处理要求	需要离线所有查询	可处理在线查询
空间复杂度	O(n+Q)	O(n)
时间复杂度	O(nα(n)+Q)	O(nα(n))
实现复杂度	较高	相对简单
适用场景	批量查询	实时单次查询

这种方法的优势在于它不需要预先知道所有查询，可以像倍增算法一样处理即时查询，同时又保持了接近线性的时间复杂度。

3. 算法正确性证明与性能分析

3.1 为什么这种方法有效

关键在于理解DFS遍历时并查集的状态变化：

当首次访问节点u时，它的并查集父节点就是自己
访问完u的所有子节点后，这些子节点都被合并到u的集合中
当查询两个节点x和y的LCA时：
- 如果其中一个节点是另一个的祖先，LCA就是祖先节点
- 否则，它们的LCA就是第一个被完全访问的共同祖先

这种机制保证了在查询时刻，并查集的find操作能够返回正确的LCA。

3.2 时间复杂度分析

该算法的时间复杂度主要取决于两个因素：

DFS遍历：O(n)
并查集操作：每次find和union操作的平均时间复杂度为O(α(n))，其中α是反阿克曼函数

因此总体时间复杂度为O(nα(n))，与经典Tarjan算法相当，但空间复杂度更低，且支持在线查询。

4. 实战应用与边界情况处理

4.1 实际编码实现要点

在实现这种算法时，有几个关键细节需要注意：

路径压缩优化：必须实现带路径压缩的find操作，否则性能会退化
查询时机：只能在两个节点都被访问后才能得到正确结果
树的无向表示：邻接表需要存储为无向图，但遍历时要避免回溯到父节点

def main(): # 示例：树结构 (1->2, 1->3, 2->4, 2->5) adj = { 1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2] } queries = [(4, 5), (3, 5), (4, 3)] uf = UnionFind(5) visited = [False] * 6 results = [0] * len(queries) # 预处理查询 query_map = {} for idx, (u, v) in enumerate(queries): query_map.setdefault(u, []).append((v, idx)) query_map.setdefault(v, []).append((u, idx)) tarjan_lca(1, query_map, adj, uf, visited, results) print(results) # 应输出 [2, 1, 1]