尽管都叫 Tarjan 算法，但用于解决 LCA（最近公共祖先）问题 和 求强连通分量 的实际上是两种不同的算法。它们由同一位作者 Robert Tarjan 提出，但针对的是不同的图论问题。

1. Tarjan 算法求解 LCA 基本思想 Tarjan 算法用于在线性时间内离线求解 LCA 问题。它利用深度优先搜索（DFS）和并查集（Disjoint Set Union, DSU），在一次 DFS 中处理所有的查询请求。其核心在于使用并查集动态维护节点的祖先关系。

时间复杂度 预处理：O(n+m)，其中 n 是节点数，m 是查询的数量。 查询回答：每次查询的时间复杂度接近于常数（取决于并查集操作的效率，采用路径压缩与按秩合并后可近似认为是 O(1)）。 主要步骤 对树进行一次 DFS。 在访问每个节点时，将该节点标记为已访问，并将其所有子节点加入到一个待处理查询列表中。 当回溯到某节点时，使用并查集将该节点的所有子节点与其自身合并。 若某个查询涉及的两个节点均已访问，则通过查找这两个节点所在集合的代表元素来确定它们的最近公共祖先。 2. Tarjan 算法求强连通分量（SCC） 基本思想 Tarjan 算法用于寻找有向图中的所有强连通分量（Strongly Connected Components, SCC）。它基于深度优先搜索，并利用递归栈和一个特殊的索引来追踪当前节点是否在一个新的强连通分量中。

时间复杂度 整体时间复杂度为 O(n+e)，其中 n 是节点数，e 是边数。 主要步骤 执行一次深度优先搜索遍历整个图。 维护一个递归栈以及每个节点的发现时间、低值（Low Link Value）。 当从一个节点开始的探索结束时，如果该节点的低值等于其发现时间，那么从递归栈中弹出的所有节点构成一个强连通分量。 3. 比较 特性/算法 Tarjan LCA Tarjan SCC 应用场景 树或森林中的 LCA 查询 有向图中的强连通分量 数据结构依赖 并查集（DSU） 递归栈、发现时间、低值 时间复杂度
O(n+m) O(n+e) 是否在线 离线（需要预先知道所有查询） 在线 虽然两者都名为 Tarjan 算法，且都采用了深度优先搜索作为基础，但它们分别解决了完全不同的问题，使用的具体技术和数据结构也有所不同。了解这些差异有助于正确选择合适的算法来解决问题。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com