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

【板子】LCA Tarjan

news 2026/7/28 10:26:41

这是一份基于 Tarjan（塔扬）算法的最近公共祖先（LCA）模板及详细讲解。该算法利用离线处理和并查集的思想，是目前求解 LCA 问题最高效的算法之一（时间复杂度 O(N+Q)，其中 N 为节点数，Q 为询问数）。

1. 算法核心讲解

核心思想：离线 + 并查集

Tarjan 算法是一种离线算法，意味着你需要先读入所有的查询请求，然后一次性处理完所有答案，而不是像在线算法那样问一个答一个。

它的巧妙之处在于利用了深度优先搜索（DFS）回溯时的信息，结合并查集来维护当前的“祖先”关系。

算法步骤解析

初始化：
- 每个节点的父节点指向自己（fa[i] = i）。
- 标记所有节点未访问（vis[i] = false）。
深度优先搜索 (DFS)：
- 进入节点时：标记当前节点u为已访问（vis[u] = true）。
- 递归子节点：遍历u的所有子节点v。如果v未被访问，则递归处理v，并在回溯时将v的父节点指向u（合并集合）。
- 处理查询（关键步骤）：当从子节点回溯到当前节点u时，检查所有以u为端点的查询(u, v)。如果节点v已经被访问过（说明v所在的子树已经遍历完毕），那么v当前的并查集根节点find(v)就是u和v的最近公共祖先（LCA）。

为什么这样做是对的？

当 DFS 回溯到节点u时，意味着u的子树已经全部遍历完成。此时，所有在u子树中的节点，它们的并查集都会指向u（或者u的某个祖先）。如果此时发现查询的另一个节点v已经被访问过，说明v不在当前子树中，那么它们的公共祖先只能是当前路径上深度较浅的那个节点，也就是此时的并查集根节点。

2. C++ 代码模板

这是一个通用的 Tarjan LCA 模板，支持多组查询。

#include <iostream> #include <vector> #include <cstring> using namespace std; const int N = 50010; // 节点最大数量 const int M = 1000010; // 查询最大数量 // 存图：邻接表 vector<int> e[N]; // 存查询：query[u] 中存储 pair<查询的另一个点, 查询的ID> vector<pair<int, int>> query[N]; int fa[N]; // 并查集数组 bool vis[N]; // 访问标记数组 int ans[M]; // 存储查询结果，ans[id] 表示第 id 个查询的答案 // --- 并查集模板 --- int find(int u) { if (u == fa[u]) return u; return fa[u] = find(fa[u]); // 路径压缩 } // --- Tarjan 算法核心 --- void tarjan(int u) { vis[u] = true; // 1. 进入节点 u，标记为已访问 // 2. 遍历所有邻接点（子节点） for (auto v : e[u]) { if (!vis[v]) { tarjan(v); // 递归处理子树 fa[v] = u; // 回溯时，将子节点指向父节点（合并集合） } } // 3. 处理所有以 u 为起点的查询 for (auto q : query[u]) { int v = q.first; int id = q.second; // 如果另一个节点 v 已经被访问过，说明找到了 LCA if (vis[v]) { ans[id] = find(v); // find(v) 即为 u 和 v 的最近公共祖先 } } } int main() { int n, m; // n 个节点，m 个查询 cin >> n >> m; // 初始化并查集和访问标记 for (int i = 1; i <= n; i++) { fa[i] = i; vis[i] = false; } // 读入 n-1 条边 for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; e[a].push_back(b); e[b].push_back(a); } // 读入 m 个查询 for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; // 为了处理双向查询，将 (b, i) 存入 a 的列表，(a, i) 存入 b 的列表 query[a].push_back({b, i}); query[b].push_back({a, i}); } // 从根节点（通常设为1）开始跑 Tarjan tarjan(1); // 输出结果 for (int i = 1; i <= m; i++) { cout << ans[i] << endl; } return 0; }

3. 复杂度分析

时间复杂度：
- DFS 遍历：遍历整棵树，复杂度为 O(N)。
- 并查集操作：每次find操作近似 O(1)（路径压缩后）。
- 处理查询：每个查询被处理两次（存正反两个方向），总复杂度为 O(Q)。
- 总计：O(N+Q)。
空间复杂度：O(N+Q)，主要用于存储图、查询列表和并查集数组。