这里的Tarjan算法是用于解决LCA问题的离线算法，在《算法训练营：海量图解+竞赛刷题（入门篇）》中会讲解求连通分量的Tarjan算法。在线算法指每读入一个查询（求一次LCA就叫作一次查询），都需要运行一次程序得到本次查询答案。若一次查询需要 O (log n )时间，则 m 次查询需要 O ( m log n )时间。离线算法指首先读入所有查询，然后运行一次程序得到所有查询答案。Tarjan算法利用并查集优越的时空复杂性，可以在 O ( n + m )时间内解决LCA问题。

1. Tarjan算法

（1）初始化集合号数组和访问数组，fa[ i ]= i ，vis[ i ]=0。

（2）从 u 出发深度优先遍历，标记vis[ u ]=1，深度优先遍历 u 所有未被访问的邻接点，在遍历过程中更新距离，回退时更新集合号。

（3）当 u 的邻接点全部遍历完毕时，检查关于 u 的所有查询，若存在一个查询 u 、 v ，而vis[ v ]=1，则利用并查集查找 v 的祖宗，找到的节点就是 u 、 v 的最近公共祖先。

2. 完美图解

在树中求5、6的最近公共祖先，求解过程如下。

（1）初始化所有节点的集合号都等于自己，fa[ i ]= i ，vis[ i ]=0。

（2）从根节点开始深度优先遍历，在遍历过程中标记vis[]=1。

（3）8号节点的邻接点已访问完毕，更新fa[8]=6，没有8相关的查询，回退到6。

（4）遍历6号节点的下一个邻接点9，标记vis[9]=1，9号节点的邻接点已访问完毕，更新fa[9]=6，没有9相关的查询，回退到6。

（5）6号节点的邻接点已访问完毕，更新fa[6]=4，有6相关的查询5（查询5 6），但是vis[5]≠1，什么也不做，返回到4。

（6）4号节点的邻接点已访问完毕，更新fa[4]=2，没有4相关的查询，返回到2。

（7）遍历2号节点的下一个邻接点5，标记vis[5]=1，继续深度遍历到7，标记vis[7]=1，7号节点的邻接点已访问完毕，更新fa[7]=5，没有7相关的查询，回退到5。

（8）5号节点的邻接点已访问完毕，更新fa[5]=2，有5相关的查询6（查询5 6），且vis[6]=1，此时需要从6号节点开始使用并查集查找祖宗。

（9）从6号节点开始利用并查集查找祖宗的的过程如下。首先判断6的集合号fa[6]=4，找4的集合号fa[4]=2，找2的集合号fa[2]=2，找到祖宗（集合号为其自身）后返回，并更新祖宗到当前节点路径上所有节点的集合号，即更新6、4的父节点fa[4]=2，fa[6]=2，此时fa[6]就是5和6的最近公共祖先。

总结： 在当前节点 u 的邻接点已访问完毕时，检查 u 相关的所有查询 v ，若vis[ v ]≠1，则什么也不做；若vis[ v ]=1，则利用并查集查找 v 的祖宗，lca( u , v )=fa[ v ]。实际上， u 的祖宗就是 u 向上查找第1个邻接点未访问完的节点，它的fa[]还没有更新，仍满足fa[ i ]= i ，它就是 v 的祖宗。

3. 算法实现

4. 算法分析

离线Tarjan算法用到了并查集的优越性， m 次查询的时间为 O ( n + m )。 PjiCPyZvERpta20R5uimm+f3rlN1KN7nspDXEpIA4Bi+obM1xGq1A5WkY2hvQefz