最近公共祖先Tarjan算法

最近公共祖先（Lowest Common Ancestor, LCA）问题是指在给定一棵树中找到两个节点的最短路径上的共同祖先。Tarjan算法通常用于解决这个问题，但它的主要目的是为了发现图中的强连通分量（Strongly Connected Components, SCC），而不是直接计算LCA。不过，由于这两种问题都涉及到深度优先搜索和拓扑排序的思想，所以我们可以借助Tarjan算法的思路来理解LCA。

Tarjan的算法是基于深度优先搜索和一种称为“DFS树”的数据结构。在寻找LCA的过程中，如果能找到两个节点在同一棵DFS树或它们的DFS祖先相同，那么这两个节点就是最近公共祖先。这里的关键在于维护节点的前驱（pred）和后继（succ）指针，以及一个秩（rank）数组来判断边的方向，以确定节点是否构成一个回路。

下面是 Tarjan 算法的主要步骤：

1. 初始化：对于每个未访问的节点 u，设置其秩 rank[u] = 次序号（u 的编号），低link[u] = u（表示 u 的父节点），深度 depth[u] = 0，访问次数和栈顶指针为 null。

2. DFS 递归过程：从根节点开始遍历，对每个子节点 v，执行以下操作：
a. 如果 v 没有被访问过，则进行一次深度优先搜索，更新深度、秩和低link信息。
b. 记录 v 的秩 rank[v] 和当前的深度 depth[v]，并将 v 加入到相应的 DFS 树。
c. 更新 v 的所有前驱和后继指针。
d. 如果 v 是回路的一部分，将 v 设置为它自身的低link，这会导致算法在下一个阶段检测到回路。

3. 完成搜索后，对每个节点 u，检查 lowlink[u] 是否等于 u，如果是，说明 u 和 u 是同一个强连通分量内的节点。同时，这也帮助我们找到 u 和其他节点的最近公共祖先，因为他们在同一棵树上。