Tarjan作为一位算法大师，发明了许多算法。本篇博文介绍一下Tarjan框架下的求解树上LCA（最近公共祖先）的离线算法，复杂度O(N+Q)。以及求割点，桥的算法，复杂度O(V+E),即dfs 1次所需的时间。
一棵树，n个节点，Q组询问（x，y），求x,y的LCA
最暴力的想法，x,y都向上搜索，因为向上的节点就是x或y的祖先，所以搜到的第一个公共节点就是x和y的LCA，复杂度O(QN)；
一种简单的优化方法是把关于x的所有询问一起处理，这样x只需要向上搜索1次，优化一下常数；
任何题目的方法归根结底都是枚举，我们注意到之前我们是在枚举询问，规模为O(Q)，一般Q是O(N^2)级别的，所以我们似乎可以换一下思路，去枚举一下答案，也就是LCA，这个的规模只是O(N)。——————————在观察我们发现u的不同子树中的节点的LCA是u，这样，一个想法就形成了。现在让我们来看一下算法导论中完整版的dfs：
//CLRS 中文版 p350 dfs模板; dfs(G) { for each vertex u in G.v u.color=WHITE u.pre=NIL time=0 for each vertex u in G.v if u.color==WHITE dfs_visit(G,u); } dfs_visit(G,u) { time=time+1 u.d=time u.color=GRAY for each v in G:Adj[u] if v.color==WHITE v.pre=u dfs_visit(G,v) u.color=BLACK time=time+1 u.f=time }请读者仔细阅读这段伪代码，这几乎是在全面的前提下最精简的版本了，少了任何一句话都不行，尤其是其中的“白”“灰”“黑”三种颜色与时间戳的概念，在很多高级算法中是必不可少的，也是很多高级算法创造根源，Tarjan_LCA算法在这个基础上就很容易理解。
来个例子，本例子中，x1 < x2 < x3 < x4 < x5 < x6 画出时间戳可以发现u，v的时间戳不相交，这样我们可以轻易得出以下定理：
当出现“灰黑灰”时，x为u向上第一个灰点，则path(u,x)上的点和v的LCA为x。 简单来说就是上面的直觉，x下一颗子树u内节点与另外子树中节点的LCA均为x 这样的性质让我们想到了一种数据结构——并查集 废话不多说，上CLRS伪代码： LCA(u) MAKE_SET(u); FIND_SET(u).ancestor=u; for each child v of u in T LCA(v) UNION(u,v) FIND_SET(u).ancestor=u u.color=BLACK for each node v such that (u,v) in P if v.color==BLACK print "The least common ancestor of" u "and" v "is" FIND_SET(v).ancestorhttp://www.cnblogs.com/JVxie/p/4854719.html 这个网站有比较详细的模拟过程，可以看一看加深理解 http://blog.csdn.net/jarily/article/details/8947928 再转一份比较清晰的解释： *算法思想: *Tarjan_LCA离线算法; *Tarjan算法基于dfs的框架,对于新搜到的一个结点,首先创建由这个结点构成的集合,再对当前结点的每个子树进行搜索; *每搜索完一棵子树,则可确定子树内的LCA询问都已解决,其他的LCA询问的结果必然在这个子树之外; *这时把子树所形成的集合与当前结点的集合合并,并将当前结点设为这个集合的祖先; *之后继续搜索下一棵子树,直到当前结点的所有子树搜完; * *这时把当前结点也设为已被检查过的,同时可以处理有关当前结点的LCA询问; *如果有一个从当前结点到结点v的询问,且v已经被检查过; *则由于进行的是dfs,当前结点与v的最近公共祖先一定还没有被检查; *而这个最近公共祖先的包含v的子树一定已经搜索过了,那么这个最近公共祖先一定是v所在集合的祖先; * *算法步骤: *对于每一个结点: *(1)建立以u为代表元素的集合; *(2)遍历与u相连的结点v,如果没有被访问过,对于v使用Tarjan_LCA算法,结束后将v的集合并入u的集合; *(3)对于与u有关的询问(u,v),如果v被访问过,则结果就是v所在集合的代表元素;
习题： 模板题： 1.poj 1330 2.http://acm.zjnu.edu.cn/CLanguage/showproblem?problem_id=1232 交通运输线
