一、定义与定理
LCA：Least Common Ancestors（最近公共祖先），对于一棵有根树T的任意两个节点u，v，求出LCA(T, u, v)，即离跟最远的节点x，使得x同时是u和v的祖先。
在线算法：用比较长的时间做预处理，但是等信息充足以后每次回答询问只需要用比较少的时间。
离线算法：先把所有的询问读入，然后一起把所有询问回答完成。
RMQ：给出一个数组A，回答询问RMQ(A, i, j)，即A[i...j]之间的最值的下标。
二、DFS+RMQ
1）Sparse Table（ST）算法
描述：
1 //初始化
2 INIT_RMQ
3 //max[i][j]中存的是重j开始的i个数据中的最大值，最小值类似，num中存有数组的值
4 for i : 1 to n
5 max[0][i] = num[i]
6 for i : 1 to log(n)/log(2)
7 for j : 1 to n
8 max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]
9 //查询
10 RMQ(i, j)
11 k = log(j-i+1) / log(2)
12 return MAX(max[k][i], max[k][j-2^k+1])
分析：初始化过程实际上是一个动态规划的思想。易知，初始化过程效率是O(nlogn)，而查询过程效率是O(1)。ST是一个在线算法。
示例：POJ 3368 解题报告
2）求解LCA问题
描述：
（1）DFS：从树T的根开始，进行深度优先遍历，并记录下每次到达的顶点。第一个的结点是root(T)，每经过一条边都记录它的端点。由于每条边恰好经过2次，因此一共记录了2n-1个结点，用E[1, ... , 2n-1]来表示。
（2）计算R：用R[i]表示E数组中第一个值为i的元素下标，即如果R[u] < R[v]时，DFS访问的顺序是E[R[u], R[u]+1, ..., R[v]]。虽然其中包含u的后代，但深度最小的还是u与v的公共祖先。
（3）RMQ：当R[u] ≥ R[v]时，LCA[T, u, v] = RMQ(L, R[v], R[u])；否则LCA[T, u, v] = RMQ(L, R[u], R[v])，计算RMQ。
由于RMQ中使用的ST算法是在线算法，所以这个算法也是在线算法。
示例：ZOJ 3195 解题报告。
三、Tarjan算法
描述：Tarjan算法是一个离线算法，也就是说只有先获得所有的查询，再按一个特定的顺序进行运算。
1 //parent为并查集，FIND为并查集的查找操作
2 Tarjan(u)
3 visit[u] = true
4 for each (u, v) in QUERY
5 if visit[v]
6 ans(u, v) = FIND(v)
7 for each (u, v) in TREE
8 if !visit[v]
9 Tarjan(v)
10 parent[v] = u
示例：HDOJ 2586 解题报告。
posted on 2009-07-04 15:25
Icyflame 阅读(6873)
评论(0) 编辑 收藏 引用 所属分类:
图论