SGi's Blog

Google 2008编程挑战赛已顺利结束，清华大学计算机系的楼天城获得第一名，南京外国语学校的朱泽园获得第二名。进入最终决赛的一百位选手中有19位来自中国。从Google搜索结果来看，楼天城和朱泽园都有过集训参加国际奥林匹克竞赛的经历，其中楼天城与其他两位选手组成清华代表队参加了2007年ACM国际大学生程序设计竞赛，并获得第二名。

膜拜大牛~

最近公共祖先（LCA）问题都应该很熟悉了。

LCA（T，u，v）：在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先

LCA问题可以用朴素的DFS方法解决，但是时间复杂度就很高了，这里介绍一种高级一点的解决LCA问题的Tarjan算法。

Tarjan算法是由Robert Tarjan在1979年发现的一种高效的离线算法，也就是说，它要首先读入所有的询问（求一次LCA叫做一次询问），然后并不一定按照原来的顺序处理这些询问。

首先需要有一些预备知识：

1.基本图论

这个就不多讲了，如果有不知道的可以随便抓一本数据结构的书恶补一下。

2.并查集

并查集其实也是很简单的东西，实现的代码都不超过10行。

这里提一下并查集的概念，并查集是一种处理元素之间等价关系的数据结构，一开始我们假设元素都是分别属于一个独立的集合里的，主要支持两种操作：

1. 合并两个不相交集合(Union)
2. 判断两个元素是否属于同一集合(Find)

需要知道一点，就是并查集的Find操作的时间复杂度是常数级别的。

考察树T中所有与结点u有关的询问(u, v)

对于子树u中的结点v，满足LCA(u, v) = u

对于子树p1而非子树u中的结点v，满足LCA(u, v) = p1

对于子树p2而非子树p1中的结点v，满足LCA(u, v) = p2

算法DFS有根树T，定义从根节点到当前正在遍历的结点u的路径为活跃路径P
对于每个已经遍历过的结点x，我们用并查集将其连接到P上距离其最近的结点Find(x)

记录与u有关的询问集合为Q(u)

对于Q(u)中的任意一组询问LCA(u, v)，如果v已经遍历过，那么答案就是Find(v)，所以我们只需要维护当前所有以遍历结点的F即可。

第一次遍历结点u时，有Find(u) = u；
遍历完子树u后，子树u内任意结点v均有F(v) = u；回溯回结点p1时，子树u内任意结点v均有F(w) = p1，使用并查集完成即可。

算法流程：

Tarjan(u)
F(u)<-u；
For each (u,v) in Q(u) do Answer(u,v) <- F(v)
For each v in son(u)
a) Tarjan(v)；
b) F(v) <- u；

这里的F用并查集来实现。

这样LCA的Tarjan算法就可以完整的实现了，这个算法的时间复杂度取决于并查集Find操作的时间复杂度，如果采用不相交集森林的方法来实现并查集并采用路径压缩来优化，这样Find操作的时间复杂度可以认为是常数级别的。

所以Tarjan算法的时间复杂度就是O(Na(N) + Q)，a(N)在可以计算的范围内是一个小于4的常数，空间复杂度为O(N)，其中N表示问题规模，Q表示询问次数。