Tarjan算法 （以发现者Robert Tarjan命名）是一个在图中寻找强连通分量的算法。算法的基本思想为：任选一结点开始进行深度优先搜索dfs（若深度优先搜索结束后仍有未访问的结点，则再从中任选一点再次进行）。搜索过程中已访问的结点不再访问。搜索树的若干子树构成了图的强连通分量。
应用到咱们要解决的LCA问题上，则是：对于新搜索到的一个结点u，先创建由u构成的集合，再对u的每颗子树进行搜索，每搜索完一棵子树，这时候子树中所有的结点的最近公共祖先就是u了。
引用此文的一个例子，如下图（不同颜色的结点相当于不同的集合）：
假设遍历完10的孩子,要处理关于10的请求了，取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10，集合的祖先便是关键路径上距离集合最近的点。
比如：
- 1，2，5，6为一个集合,祖先为1，集合中点和10的LCA为1
- 3，7为一个集合，祖先为3，集合中点和10的LCA为3
- 8，9，11为一个集合，祖先为8，集合中点和10的LCA为8
- 10，12为一个集合，祖先为10，集合中点和10的LCA为10
得出的结论便是：LCA(u,v)便是根至u的路径上到节点v最近的点。
2.2、Tarjan算法如何而来
但关键是 Tarjan算法是怎么想出来的呢？再给定下图，你是否能看出来：分别从结点1的左右子树当中，任取一个结点，设为u、v，这两个任意结点u、v的最近公共祖先都为1。
于此，我们可以得知：若两个结点u、v分别分布于某节点t 的左右子树，那么此节点 t即为u和v的最近公共祖先。更进一步，考虑到一个节点自己就是LCA的情况，得知：
- 若某结点t 是两结点u、v的祖先之一，且这两结点并不分布于该结点t 的一棵子树中，而是分别在结点t 的左子树、右子树中，那么该结点t 即为两结点u、v的最近公共祖先。
这个定理就是Tarjan算法的基础。
一如上文1.1节我们得到的结论：“如果当前结点t 满足 u <t < v，说明u和v分居在t 的两侧，故当前结点t 即为最近公共祖先”。
而对于本节开头我们所说的“如果要求多个任意两个结点的最近公共祖先，则相当于是批量查询”，即在很多组的询问的情况下，或许可以先确定一个LCA。例如是根节点1，然后再去检查所有询问，看是否满足刚才的定理，不满足就忽视，满足就赋值，全部弄完，再去假设2号节点是LCA，再去访问一遍。
可此方法需要判断一个结点是在左子树、还是右子树，或是都不在，都只能遍历一棵树，而多次遍历的代价实在是太大了，所以我们需要找到更好的方法。这就引出了下面要阐述的Tarjan算法，即每个结点只遍历一次，怎么做到的呢，请看下文讲解。
2.3、Tarjan算法流程
Tarjan算法流程为：
Procedure dfs（u）；
begin
设置u号节点的祖先为u
若u的左子树不为空，dfs（u - 左子树）；
若u的右子树不为空，dfs（u - 右子树）；
访问每一条与u相关的询问u、v
-若v已经被访问过，则输出v当前的祖先t（t即u,v的LCA）
标记u为已经访问，将所有u的孩子包括u本身的祖先改为u的父亲
end
普通的dfs 不能直接解决LCA问题，故Tarjan算法的原理是dfs + 并查集，它每次把两个结点对的最近公共祖先的查询保存起来，然后dfs 更新一次。如此，利用并查集优越的时空复杂度，此算法的时间复杂度可以缩小至O(n＋Q)，其中，n为数据规模，Q为询问个数。
2.4、Tarjan算法的应用举例
引用此文中的一个例子。
i) 访问1的左子树
|
STEP 1：从根结点1开始，开始访问结点1、2、3 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
2 |
3 |
|||||
|
STEP 2：2的左子树结点3访问完毕 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
2 |
2 |
|||||
|
STEP 3：开始访问2的右子树中的结点4、5、6 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
2 |
2 |
4 |
5 |
|||
|
STEP 4：4的左子树中的结点5访问完毕 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
2 |
2 |
4 |
4 |
|||
|
STEP 5：开始访问4的右子树的结点6 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
2 |
2 |
4 |
4 |
6 |
||
|
STEP 6：结点4的左、右子树均访问完毕，故4、5、6中任意两个结点的LCA均为4 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
2 |
2 |
4 |
4 |
4 |
||
|
STEP 7：2的左子树、右子树均访问完毕，故2、3、4、5、6任意两个结点的LCA均为2 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
2 |
2 |
2 |
2 |
2 |
||
如上所述：进行到此step7，当访问完结点2的左子树（3），和右子树（4、5、6）后，结点2、3、4、5、6这5个结点中，任意两个结点的最近公共祖先均为2。
ii) 访问1的右子树
|
STEP 8：1的左子树访问完毕，开始访问1的右子树 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
1 |
1 |
1 |
1 |
1 |
||
|
STEP 9：开始访问1的右子树中的结点7、8 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
1 |
1 |
1 |
1 |
1 |
7 |
|
|
STEP 10 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
1 |
1 |
1 |
1 |
1 |
7 |
8 |
|
STEP 11 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
1 |
1 |
1 |
1 |
1 |
7 |
7 |
|
STEP 12：1的右子树中的结点7、8访问完毕 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
当进行到此step12，访问完1的左子树（2、3、4、5、6），和右子树（7、8）后，结点2、3、4、5、6、7、8这7个结点中任意两个结点的最近公共祖先均为1。
|
STEP 13：1的左子树、右子树均访问完毕 |
||||||||
|
节点 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
祖先 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
